# pathfinding on a 2d map

This topic is 1239 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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

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.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• ### Forum Statistics

• Total Topics
631425
• Total Posts
3000011
×