4 ms·

For me, figuring out how to implement A* on a world was one of those programming milestones along the way of me grokking how software is put together. In fact,

For me, figuring out how to implement A* on a world was one of those programming milestones along the way of me grokking how software is put together. In fact, I see there's a Stack Overflow question from me still online with an implementation I wrote in Python eight years ago (https://stackoverflow.com/questions/4159331/python-speed-up-an-a-star-pathfinding-algorithm https://stackoverflow.com/questions/4159331/python-speed-up-...), and I have sometimes wondered how many people have then used that old snippet as a reference. Amit's articles were online then, and definitely helped me think through these problems, and their main strength is just how visual the explanations all are. I'm pleased to see they're still online, being updated, and no doubt benefitting others, I know that personally Amit's effort was one of a number of things that has allowed me to be a full-time indie game developer all these years later.

rcarmo 8y ago
I can relate to that feeling - I cut my teeth on A* in Standard Pascal nearly a quarter of a century ago as a freshman, and the equivalent LISP was so tiny and concise to be a thing of beauty.
amitp 8y ago
Glad to hear it! :)
cmroanirgo 8y ago
A 3D RTS I worked on in the mid 90's used A* in a couple of ways to do pathfinding. 1. First generation was to use a series of 'way points' that was created with the landscape/level generator itself. They were the basic 'paths of best flow' in a very broad sense. It was used when a player sent troops from one side of the map to the other. There was only 20-40 of these on a map. 2. Second generation used a much finer granularity that was a lookup of preprocessed surface normals on the terrain. So, the tank/unit would look at the waypoints to know generally which way is the 'best ish' way, and use a finer grained one for the first and last mile. We also used collision avoidance schemes so you could pass one group of vehicles 'thru' another and they'd miss one another in a logical way (ie small deviations left/right based upon own vs. other speed). We ended up not using the 'one vehicle per square' technique that may RTS used at the time -- we didn't need to.

rcarmo 8y ago

I can relate to that feeling - I cut my teeth on A* in Standard Pascal nearly a quarter of a century ago as a freshman, and the equivalent LISP was so tiny and concise to be a thing of beauty.

amitp 8y ago

Glad to hear it! :)

cmroanirgo 8y ago

A 3D RTS I worked on in the mid 90's used A* in a couple of ways to do pathfinding. 1. First generation was to use a series of 'way points' that was created with the landscape/level generator itself. They were the basic 'paths of best flow' in a very broad sense. It was used when a player sent troops from one side of the map to the other. There was only 20-40 of these on a map. 2. Second generation used a much finer granularity that was a lookup of preprocessed surface normals on the terrain. So, the tank/unit would look at the waypoints to know generally which way is the 'best ish' way, and use a finer grained one for the first and last mile. We also used collision avoidance schemes so you could pass one group of vehicles 'thru' another and they'd miss one another in a logical way (ie small deviations left/right based upon own vs. other speed). We ended up not using the 'one vehicle per square' technique that may RTS used at the time -- we didn't need to.