Pathfinding, A*, Motivation and Progress

As you might have concluded from my last journal post, I got demotivated when I hit a snag in my self-devised pathfinding algorithm based on the A* principle of pathfinding. I knew that A* was going to be a simple, straight-forward and decidedly stupid way of finding a path, but I wanted to understand the principles of it before I migrated on to adding “costs” to the logic of the algorithm and making it smarter. I was shocked to see that with the relatively simple map that we had created, roughly 34×58 tiles large, finding a single target from one side of the map to the other made PHP run out of its allotted memory. And so, it took a few days for me to pick up the deving and figure out what was going wrong.

It turns out that when I started to examine the path that was returned for a relatively short example, that there were some mistakes. It returned some tiles as part of the path that weren’t supposed to be. Then I took a look at the examined tiles and there were way more than I thought there should have been. It turned out the algorithm wasn’t ignoring blocking tiles as it should be. When I had found the problem and fixed it, I found the load was cut by more than 50%. That was good, but it’s not good enough. I’m going to examine it some more soon, but it means there is still progress to be made before I start implementing the costs structure. Perhaps when I’m no longer able to streamline things, I’ll show you guys what I came up with.

Anyway, reinvigorated motivation FTW.

Leave a Reply