This time I'm going to take the example of other people doing a gig similar to mine and try to break down the problem and what went into solving it for those of you who aren't programmers. This should still be entertaining for those of you who are programmers though. This will help make following this series more of an interesting set of problems and solutions and less of a screenshot log. Buckle up, this is going to be a kind of long but still awesome ride.
Path finding is an essential feature for any game that requires AI agents to move about a world or level. Infiltrator definitely needs enemies to be able to plot a course from one place to another, so that means I have to get some kind of path finding algorithms setup. The first step is to create a grid that contains data about the environment which agents will be travelling through. Each cell of the grid can be either "walkable," or "un-walkable," providing all AI's with a public matrix which they can use the data from to plot a path. The level module then automatically calculates which tiles will be un-walkable based on the objects in the level map. Obviously this doesn't make the game tile based. The only tile based part of the game is how the enemies figure out how to get from point A to point B without wasting money on gas.
The next step is to go on Google and hope there are some quick and maybe slightly unclean path finding algorithms that 2D game programmers use. Luckily, path finding has been around forever, so after reading a few papers on the subject I have a working knowledge of my chosen technique, D* light. I read a few code examples and tutorials and then create my personal module to handle the algorithm with it's own grid separate from the level grid. I lift whole pages of code from some places and only tweak them. I make sure I fully understand the underlying workings of the code and D* lite so that no problems come up as a result of my failure to know what my code is doing.
It's easy to setup the grid to draw another color of tile for cells that are part of an enemy's path. This gives me a visual representation of what's going on inside the AI's mind. I add a few lines of code to the drone with orders to plot a path to the player. I compile the program and hope for the worst. The result is what brought me up to session number 17, where the enemies appeared to be plotting a path straight for the player and ignoring the obstacles.
The good news was that what happened was far from the worst. The bad news was that I had no idea this was the case. Since I had no way of testing the path finding code until that point, the bug could have been almost anywhere. Maybe I screwed up the algorithms in the path finding code, or maybe the drones weren't using the path finding engine right. The problem could even have been in how the level was drawing and interpreting the grid, which would mean the path finding engine was fine.
This bug nearly drove me insane. I checked over every single part of the code time and time again, but still couldn't find issue with it anywhere. After awhile I managed to create a simple example program that tested my path finding module on it's own. This made a huge difference, as it confirmed that my path finding engine was a-okay and the problem was with the drone module or with how the level module was setting up the grid. After hours of debugging tactics, I still couldn't even figure out which module was responsible for the problem.
The path to the solution came in an unexpected form. I'd kind of given up on solving the bug. I was mindlessly clicking through my source files knowing full well that I wasn't going to notice the bug that way. I was just using what little brain power I had left which was no more than the will to find the bug. Then I saw this one sub-routine(technically called a method) in the level module. It was the section that calculated which tiles were supposed to be walkable and which were not. It was simple really. For every barrier(wall) in the level file, it set the tile at the top left corner of said wall to be un-walkable in the D* lite and level grid. Then it stepped through and uses some fancy math to set all tiles the barrier is touching to be unwalkable in the level grid. And only the level grid.
FACE, PALM
The level grid is the one that is used to draw the colored tiles on the screen. I was seeing the right tiles on screen as being un-walkable, but the path finding engine was only seeing the top left tile for every barrier. The fix was simply to add a single line of code which would also set the D* grid tiles touching each barrier to be un-walkable.
Save, compile, test, and post online about it. Don't like the tiled look? It's easy to get rid of.
This bug reflects a little badly on my decision to have the level and the D* engine keep their own personal grid. A lot of code gets copy-pasted and slightly changed to do the same thing with both grids. If this is a bad design decision(which it probably is,) it needs to be dealt with before it becomes tangled into the code in a way which would be extremely laborious to remove.
Aside from that, the next step is obviously to setup the enemies to follow their path. Drone enemies are supposed to just go straight to the player and shoot whenever they have a good line of sight. Mix that with the fact that I can easily apply an acceleration in any direction to any game object since I use Box2D, and you have a recipe for an easy feature to add. I'll have to choose some other junk from the $5 feature bin before I conclude the next session, but for now I have a direction to travel and the means to travel it.
--LazerBlade
No comments:
Post a Comment