I am trying to implement A* pathfinding however I am not sure how to determine which cells in the world grid should be walkable/unwalkable. Right now I get me terrain/geometry by tracing an image, getting the contour and generating the terrain/physical body from this. How could I do this? Any info is much appreciated. Thanks.

Obviously that depends on the kind of terrain data you are reading but in the end it is all down to your guts. You can start by defining a certain degree of slope as "unwalkable", the same goes for water oder desert / muds / swamps if you have those terrain features.

Unfortunately you would need to check all height values you sample from your images but you can of course stop checking a cell once you found it unwalkable.

Oh sorry this is for a 2d game. I suppose the terrain data would be the png image, anything other than alpha being unwalkable. Once I generate my the physical body of my terrain/world how could I know which cells in the grid should be unwalkable, if all I have is the image, the contour of the physical body, the position of the physical bodies.

What I mean is, as in the following image. Once I setup my grid and my geometry, is there a way in which I could determine which cells contain geometry so as to set them as 'unwalkable'.

Cells enclosed in red = unwalkable.
http://img190.imageshack.us/img190/3577/unwalkable.jpg


[Edited by - Antonym on July 26, 2009 4:52:10 PM]

Even if I do not fully grasp what you are actually doing: You already have some algorithm to determine where you place geometry (those green obstacles in your image). Then simpl calculate the 2d bounding rectangle for those green objects and check for intersection with your 2d cells. All cells intersected by 2d bounding rectangles of obstacles are unwalkable.

Is there a formula to detect cell/polygon intersection?

Well, yes: Loop through all points of your geometry and store the max and min x and y values. The final min and max (x,y) points define the geometries bounding rectangle. Then loop through each cell and check if the bounding rectangle intersects the cell's rectangle (similarly defined by a min and max point). If you are unsure how to do that give Google a run and search for "2d rectangle intersection".

Quote: Is there a formula to detect cell/polygon intersection?

Sure, if you want more exact results, you can check for intersection between the individual polygons that make up the obstacles and the AABBs that make up the grid using the separating axis test.

In a nutshell, to test a (convex) polygon against an AABB, you check to see if all the vertices of the polygon lie entirely to the left, to the right, above, or below the AABB, then check to see if the AABB lies entirely behind (or in front of, depending on how you look at it) one of the edges of the polygon. If none of these tests passes, the polygon and the AABB intersect.

Just looking at your example image, I'm thinking a navigation mesh would be a more effective search-space representation in this case. However, navmesh-based pathfinding systems are much more complicated to implement than grid-based systems (IMX, at least), so you'd probably be better off sticking with the grid (for now, at least).

[Edit: If you are going to use the grid method, I'd suggest testing the actual polygons against the grid cells rather than the polygon AABBs. This will help avoid 'false positives' and will give you a more accurate mapping between the world geometry and the grid representation.]

But that approach wouldn't work with (Edit:)concave polygons would it?

Navigation mesh, interesting, I'll look into it although I don't want to get in over my head just yet.

[Edited by - Antonym on July 27, 2009 8:23:33 AM]

Quote: But that approach wouldn't work with (Edit:)concave polygons would it?

No, you'll have to decompose any non-convex polygons into convex polygons.

From your image though, it looks like you've alread done this. Since your obstacles are triangulated, the easiest solution would probably be just to use the triangles themselves (that is, intersect the mesh triangles with the grid cells to see which cells should be marked as 'unwalkable').

Many games use a 'navmesh' which is a simplified (obviously predigested) triangle mesh used to do movement checks. The simplification decreases the size of the data your pathfinder would need to process and possibly remove 'on-the-fly slope calculations. The negatives are that there can be an over gebneralization that causes objects feet to sink below the higher detailed rendering mesh or float above it in places as well as incorrectly handle some corner clipping (but the processing saving is balanced to a 'good enough' player experience ...)


If you have moveable/deformable scenery components you will have to do some dynamic processing (AABB collision stuff...) between those dynamic components (in some MMORPG games they skip this, leaving the disconcerting happenance of players moveing right thru each other when they move)