Stop That Hero! November Development Summary

I wrote up a October challenge post-mortem at the end of the previous month, and almost an entire month has gone by. I haven’t written much, partly because I went off of my self-imposed schedule to do more game dev work at the expense of writing and reading time.

What progress have I made with Stop That Hero! in the month since?

First, I implemented my own component-based object system. I know, I know. I wrote about the frustrations of trying to implement state of the art game objects and said I would give up, but eventually I found my own way. In trying to proceed with the game’s development and putting the frustration behind me, I found that I was very close to doing the same kind of work anyway. I’ll write more about the details of my implementation in another post.

Even after I had the infrastructure for the object system, I still had to figure out how to use it. In a running game session, I understand that the game’s systems will make use of the object system and components, querying and updating them as needed, but what about initialization? Specifically, how does the hero get created? Should that object and all of its relevant components get created when the level is loaded, when the level is initialized, or as part of the first update to a new game?

Some entities will get created during the course of a game session, such as when the player creates a monster at a tower, but the hero is there from the beginning, and I was having trouble trying to figure out how to treat his creation.

I already have a number of components:

• Position (current location data)
• Sprite (the current sprite image to display)
• Spawn Point (a position where an entity will be initialized when created)
• Movement (speed and direction data)
• Targeting (a list of potential target type IDs and the current object ID targeted)
• Targetable (a target type ID)
• Pathfinding (a list of traversable terrain IDs and the current path)

With the above components, I can already see the hero moving from a start location (the spawn point) to a target, which is an object made up of only Targetable and Position components. The hero picks the nearest object with a target ID matching the set of IDs he is allowed to target, avoids obstacles such as trees and water, and moves along the path generated by the pathfinding system.

The pathfinding system was surprisingly difficult. A* is such a common algorithm, and there are plenty of code examples around. Essentially, it’s a solved problem, right? The problem was that all of the code examples and most tutorials and pseudocode were node-based, whereas I was looking for something that gave much more focus to the connections. That is, it should be possible to get from one node to another in more than one way. For example, if you have a bridge, you can jump off of it very easily but you wouldn’t be able to get back up unless there was a ladder, and climbing the ladder would cost more than jumping down. Or, if the height is great, climbing down the ladder would be less risky than jumping and potentially hurting yourself.

The book “Artificial Intelligence for Games” has a focus on connections, but the pseudocode was a little difficult to follow. When the pseudocode makes use of whitespace, it’s hard to tell what code block you’re in when the source spans multiple pages. While the book says that there is a working code example on its website, I couldn’t find any code related to the pathfinding chapter. I emailed this error but the website still doesn’t reflect it, and I haven’t heard back from anyone about it.

I thought I had my pathfinding system working since my unit tests passed. Obstacles were avoided, and short paths seemed to finish as expected. It wasn’t until I gave the hero a target about a quarter of the map away that I saw a problem:

The hero’s path is specified by the multiple hero sprites and the black line. The dotted yellow line is what I think a more appropriate path should be if the pathfinding algorithm was working correctly. I found it very odd that the path was complete yet so suboptimal. I eventually realized that part of the problem was a bug in my node sorting, and here’s the relevant line:

lessThan == costSoFar < r.costSoFar

I didn't see the problem for a long time, but I eventually posted the code online. Phil Hassey pointed out that I was testing equality instead of assigning a value. Doh! Sometimes you just need a fresh pair of eyes.

There was also another bug in that line. "Artificial Intelligence for Games" argues that you should be using the costSoFar value to sort nodes in the open list, saying it is the only value that isn't a guess. I didn't quite understand why, but I figured such a thick text book written by experts who have worked on more games than I have would know better than I would. So, here's a lesson: never implement an algorithm without understanding it. Everyone else in the world argues you should use the estimated total cost to sort nodes. After all, you're trying to guess which one will get you to the target node in the fastest way. Sorting by cost so far means that there will be a bunch of nodes, possibly in multiple directions, that can be first. Once I changed the value checked from costSoFar to totalEstimatedCost, my paths were straighter and shorter.

Still, my pathfinding system isn't working quite as I expected. The hero can only walk on grass, but other entities could fly over everything. While they might prefer flatter areas, they should still be able to fly over trees, mountains, and water. I created a hero with the ability to move over all of these different terrain types, and I was disappointed to find that the path didn't change. He was still avoiding them as obstacles.

I realized that part of the problem is how I mapped the world representation to the pathfinding graph. Does the terrain have an absolute cost, or should terrain costs be entity-specific? That is, is a mountain always harder to traverse than grass, or should a mountain troll bias towards mountains while a slime prefer the plains? If every entity had the same kind of movement restrictions, it makes sense to have absolute terrain costs. An obstacle for one will be an obstacle for another. But if some can move through water or fly in the air, does it make sense for terrain to have an absolute cost? If I give each entity weights for terrain types, why not just get rid of the absolute costs entirely since the weights are what ultimately matter? How does a game such as Advance Wars handle it?

Other issues I had to deal with included problems with using floating points versus ints. I was using floats to represent world positions for objects, which is fine, but when I was integrating different aspects of the system together, I found that other data structures were implemented using ints. I was losing all of the precision I needed, and it wasn't until I was printing out text every few lines that I could see the problem. Unit tests didn't catch this issue because separate objects and components worked just fine.

But with pathfinding and targeting working fairly well, Stop That Hero! is much further along. Once I can move an entity to an expected target, the rest of the game will hopefully come together much more quickly. Hopefully.