31–40 of 94 posts
https://www.twitch.tv/videos/233560937
Much simpler case since it is on a grid and turn based!
>DE's pathing system's findPath() function was speeded up by approx 3-4x faster vs. Age1's How would that make any impact at all given that the game ran just fine on 1997 hardware?
Something has puzzled me about pathfinding in games. There is a well-known algorithm[1] for finding an optimal path: you start at the destination, assign that a cost of 0, make a queue from the points that can reach it directly, compute for each of those points the minimum "cost of directly reaching a marked point + cost written on the marked point", and then, while the queue is nonempty, taking the point with the ch…
That sounds great, in theory! One thing I've found to be the case after making the switch from web stacks to gamedev is that theory is quite often a very different ballgame versus the practical application of the theory. For turn-based games, absolutely -- and I suspect that's why you rarely see pathfinding brought up as a big concern for turn-based games. They have plenty of time to re-compute paths, there's a perfe…
Gentle reminder to the audience that AOE1's minimum target system was a single-core Pentium-90 with 16MB RAM, so this would not have helped at all :)
For people interested in path finding, there was some fascinating research done in the 90s: http://faculty.nps.edu/ncrowe/snell2.htm They used Snell's law to design pathfinding directly on region polygons, based on ray refraction. This is in contrast to the more common type of "grid searches" (A* being the most prominent example) which superimpose a grid and then do a wavefront graph search on that. I remember implem…
I think it's more popular nowadays to do a search on an adjacency graph of polygons and then smooth the path with something like the funnel algorithm. http://digestingduck.blogspot.ca/2010/03/simple-stupid-funne...
There's another approach you can take for continuous space pathfinding, however, which is to use visibility graphs.
See http://www.cs.kent.edu/~dragan/ST-Spring2016/visibility%20gr..., for example, for some explanation and diagrams.
This is the approach I used in PathEngine (www.pathengine.com).
A lot of people are put off by the possibility for graph explosion in situations where there are a lot of obstacles in an open environment, but PathEngine works around this quite effectively by detecting these kinds of obstacles and pulling them out of the visibility graph (and pathfinding search).
The fact that this post seems to be engendered by a comment on a forum ("The pathfinding in the game is terrible.") reminds me of 'Designing Video Games is Hard Work, But the Millions of Angry Players Make It All Worthwhile' http://thehardtimes.net/harddrive/designing-video-games-hard...
In news from Spain, Generallissimo Francisco Franco is still dead.
The real fun is designing the agent's AI: exploration, avoidance, engagement ;)
Crowd Pathfinding And Steering Using Flow Field Tiles
http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd...
Flow Field Pathfinding Tutorial
Just pre-compute everything. Put your vector fields in textures at map design time and be done with it. No point in overthinking this once its a simple lookup per frame. The real fun is designing the agent's AI: exploration, avoidance, engagement ;) Crowd Pathfinding And Steering Using Flow Field Tiles http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd... Flow Field Pathfinding Tutorial http://leifnode.com/…
And for AoE you cannot precompute everything. Things you have to tackle:
- Walls being built or torn down
- Trees being chopped down, gold being mined
- Units moving as a single group, not bumping into each other, not creating a dead lock when entering a narrow passage
- Units of various sizes (ram vs. villager)
> Age1's pather's A* implementation was outright broken (the open list management was flawed, so the cheapest node wasn't always expanded upon during each iteration) What is left of A* if even that doesn't work?!?
if it was completely broken it probably wouldn't have shipped that way, so the defect meant it was probably only somewhat broken and the end result was workable.
Just pre-compute everything. Put your vector fields in textures at map design time and be done with it. No point in overthinking this once its a simple lookup per frame. The real fun is designing the agent's AI: exploration, avoidance, engagement ;) Crowd Pathfinding And Steering Using Flow Field Tiles http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd... Flow Field Pathfinding Tutorial http://leifnode.com/…
I think you're forgetting there is no map design time in Age of Empires since the maps are RNG. Also, walls, structures, and destroyed forests are critical to gameplay, so it has to be an extremely dynamic process.
There are obviously ways to improve the pathfinding, https://github.com/SFTtech/openage has many plans, but your dismissals are starting from wrong assumptions.
Just pre-compute everything. Put your vector fields in textures at map design time and be done with it. No point in overthinking this once its a simple lookup per frame. The real fun is designing the agent's AI: exploration, avoidance, engagement ;) Crowd Pathfinding And Steering Using Flow Field Tiles http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd... Flow Field Pathfinding Tutorial http://leifnode.com/…
This would not have been a great solution on the original AoE's 16MB target memory.