Jason’s babblings.

I’ve already been seeing a bit of slowdown in my game, and I have a hunch it’s because of the way I set up my core state machine and timer. But that’s not what I want to write about today. Today we’re going to use Dijkstra’s Algorithm to make our monsters smarter.

Dijkstra’s Algorithm takes points connected by lines with weights and tries to find the path between two points with the least combined weight of the connecting lines. This is trivial if there’s only one path from A to B, but not so much if there’s multiple routes. The algorithm goes something like this:

1. Start with all points’ values to infinity and not-final.
2. Set your starting point to zero and remember it as current.
3. For each point connected to current:
4. -If that point’s value is not-final, ignore it.
5. -If the point’s value is less than current’s value plus the weight of the line connecting, ignore it.
6. -Otherwise set the point’s value equal to current plus the weight of the line.
7. Mark current as finalized.
8. Pick a non-finalized point connected to current and repeat steps 3-8 until there are no more non-finalized points in the graph.

Now each point’s value is the shortest possible combined weight of the path to the starting point. To find exactly which lines to travel, just traverse backward through the lowest-valued points until you reach the destination. Easy!

The point-line paradigm can be easily applied our game map: the points are map tiles, with a line to each of the tiles surrounding it. If we mark the player’s location as the starting point and each line has 1 weight, we can determine the number of steps required to hit each map tile, and the optimum path for each tile to get back to the player. So now if we have a monster on any tile, we can chase the player around corners; instead of having the monster blocked by a wall while trying to go north-west, it can go north to get around the wall. The monster can also seek out higher valued tiles if he wants to run away from the player.

I tried three approaches to write this algorithm for the game. The first attempt was an elegant recursive algorithm, which threw a Stack Overflow error after traversing 250 lines. Next attempt worked successfully, but took about a full second to calculate each tile – much too long. After some tweaks, I had it down to 1/20th of a second. Much better.

Aside from that, I did end up rewriting the core state machine to make the game very noticeably faster. And a few more things since day 10:

• Haste status effect: you make two moves for every one enemy move.
• Slow status effect: enemies make two moves for every one of your moves.
• New slime enemy that uses the slow effect.
• Optimized how projectiles are handled.
• Fixed nasty bug when when monsters and projectiles are destroyed.
• Moved all strings into resources so they can be easily translated in the future.

Current demo: Game runs at double the previous speed, and enemies follow you without getting stuck on walls. There’s a new type of enemy that keeps slowing you until you kill it.