Comment by cclogg | Hacker News Reader

Comment by cclogg | Hacker News Reader

Parent Full thread

Last spring I went through a lot of different techniques including the one you mention about subdivision. Was working on tower defense path-finding so basically the challenge was to compute every waypoint-set's path at game-start and whenever a tower is built/sold.

I think I basically tried almost every A* trick available (rectangular symmetry reduction, HPA*, points of visibility, jump point search, etc) but ultimately I couldn't make it run fast enough on iOS for our max level size which was about 100x100. It also couldn't be multi-threaded because it needed to work with online code (synchronous tick engine)...

What ended up happening was I found a full C implementation of Jump Point Search, and it was incredibly fast! I had already moved several parts of my code to C in order to speed it up, but I guess using a higher level language like Objective-C is just way too slow to have instantaneous path-finding on a 100x100 grid. I think this was the code I found https://github.com/Bio2hazard/cJumpPointSearch

You definitely had a bug. I shipped a single-threaded A* for 3GS and up with maps created from maps of approximately 500x500 locations.

It started out completely broken, storing waypoints in Core Data and was taking upwards of four minutes to calculate a path. Switching to prefetching Core Data paths brought it down to about 90 seconds, but that's as far as it could go with so many Core Data faults firing.

What made it really fly was the change the underlying data to direct bitmap access on maps prepared from the source maps (shopping centre levels actually) and applying simple filters to generate monochrome maps where one color was walkable and another not. Then source and destination locations were obtained through the original Core Data coordinates and a quick search algorithm found the closest walkable point to both. The A* calculation took perhaps a second or two.

Not content with that we went further and drew more complicated maps with what amounted to train tracks, a network of walkable paths one pixel wide connecting every store to every store to narrow down the solution space. The result was instant A* pathfinding and it was a very neat feature in the app.

You can definitely do A* in Objective C - just get to know Instruments inside out and keep tuning. On a 5S I expect you could get away with a lot of inefficiency.

>but ultimately I couldn't make it run fast enough on iOS for our max level size which was about 100x100.

100x100? That sounds trivial to make fast enough. What was the programming language used?

Reply on news.ycombinator.com