From my initial implementation to what I have now was probably a 20x speedup. I worked hard to optimize this whole system. Water (blue) and buildings (black) are not passable. In this image, the roads have the lowest weight (orange), open areas are next (green), then farming/stockpile areas (yellow), then trees, rocks, and other obstacles (grey). For wild animals like deer, the weights are very high for roads and buildings, so they’ll generally stick to the wilderness, avoid settlements, and have no problem crossing a river. I can dynamically set these weights in game. It also makes people avoid tight clusters of trees or rocks, but if that’s the only way to go, they’ll go through them. When searching for a path, it makes the people prefer roads, but if cutting across a large farm is faster than following a road around it, the people will do it. This makes some areas easier to pass than others. The AI’s need to navigate the area to get from their home to the market and to their jobs.īesides finding a valid path around buildings, A* allows you assign weights to movement in different areas. This area has a bunch of buildings, roads, trees, bridges, and water. Because my maps are large, even an optimized implementation can’t run fast enough to handle the failing case, especially when hundreds of AI’s need to move from place to place. When the path doesn’t exist A* searches a huge section of the map, only to fail. When a path exists from point A to point B, A* finds it fast. It’s fairly easy to implement and works well.
The core of the pathfinding system is A*. I’ll think I’ve gotten it right, and two months later the game grinds to single digit frame rates because the pathfinder is working overtime, or an AI will stand dumbly in the forest and freeze to death.
Pathfinding is the one system in the game that I am constantly fixing and making better. We do it unthinking while driving in the car, walking through a city, or looking at a map of roads. Find the shortest, or a least a good path from point A to point B.
0 kommentar(er)
