# pathfinding on a 2d map

## Recommended Posts

I am working on a 3d game on a terrain made of a regular grid of vertices and faces. Some faces should not be walkable because too steep, difficult terrain, underwater etc.

My only experience with pathfinding ai so far is within a voxel world where I used a kind of floodfill(??) approach: try every possible way until finding the destination by chance and remember how to get there as fast as possible. But my map now is pretty large and destinations may be very far, so I guess this would be too slow for a large number of AIs.

Any suggestions?

##### Share on other sites

To add to what everyone has said so far, start with A*. There's essentially no difference in the pathfinding between a 2d and a 3d map, they both break down into graphs of nodes (places in the world) and edges (the connection between places). A grid map with holes in it is just missing some edges.

##### Share on other sites

Thanks for replies. I will look into this A*. Maybe it's not so different from what I already did in my other game. It will probably just come down to finding the right resolution of waypoints to get decent performance, so I might have to skip some terrain nodes between waypoints.

##### Share on other sites

I am such a fan of A* that I wrote a library for it. If you are using C++ it might be a quick way to get pathfinding working for you: https://github.com/leethomason/MicroPather

##### Share on other sites

Here is another excellent starter for A* algorithm with an implementation in Cocos2D

http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

##### Share on other sites

The "flood fill" algorithm is essentially Dijkstra's. A* is an optimisation of it.

You can use these even if you don't have a regular grid on your ground, just *pretend* that you do have such a regular grid, and run the algorithm anyway. You only need to write a function "can I pass this point", which needs to be conservative enough that your moving units can actually pass that point to its adjacent points without encountering any new obstacles - so the "can I pass this point" function might need to take into account the distance of nearby objects, and return false even if the point itself appears passable.

Anyway, give it a go, and you'll easily get something that works.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628350
• Total Posts
2982211

• 10
• 9
• 24
• 11
• 9