Daniel Petersen's Blog

Documenting my struggle to make a videogame, amongst other nonsense

Home Projects

Everybody Loves Pathfinding

Posted on 2014-12-29

I’m still working on It Always Ends In Nuclear War, which I suppose can be described as my attempt at a 4x civilization-building game. Randomly generated map of the world, small group of people founding a city at the dawn of civilization, expanding your territory, meeting other civilizations, making alliances, fighting wars, discovering technology. . . That type of thing.

I admittedly don’t have much progress to show at the moment, but I am putting in a great deal of time and effort. I think the problem is that I have incredibly high standards, and I’m never quite happy with what I come up with for the game. I want to produce something that is not only fun, but a unique take on the genre. I want to produce something that looks good graphically. It also has to be something that I can create in a reasonable amount of time.

I feel confident that I can program whatever design I come up with, but coming up with a good design is challenging. I’m working on this project by myself, so I’m very much working in a bubble. Creating something that is not a cookie cutter copy of the popular titles in the genre is hard. Doing it without having someone to talk to about the ideas is harder. I’ve settled on a few different designs in the past, prototyped them out, and hated them. I’m keeping at it, and I have confidence I’ll get there eventually, but it’s just frustrating. Frustrating and time consuming.

Graphically I like the direction I’m headed, but there’s definitely something not quite right about it. I’m about as far from an artist as one can possibly get, so I think what I’ve done so far is pretty good, but like I said, it’s still not there yet. As you can see, the current thinking is that the entire game is going to have a textureless look, possibly even going as far as to have no sprites or external images used at all. This serves a dual purpose - It takes some pressure off of me having to somehow get high quality art assets, and I also think it gives off a unique stylistic vibe.

One of the design decisions that I’ve settled on is that the game will not be turn based. It’s going to tick along at a solid rate, similar to how the game Europa Universalis works. Another design decision that I’ve settled on is that there are going to be armies, settlers, and ships roaming around the map. This provides a bit of a challenge in regard to pathfinding. I want the game to be playable on a modest computer, and given how large the maps are (84,000 tiles!), and given how many units could possibly be present on the map at a time, pathfinding needs to be trivial from a performance point of view.

I implemented a pathfinding algorithm known as a* (pronounced a-star) forever ago, and it miraculously still works with It Always Ends In Nuclear War after all the changes I’ve made to the code (check out the above screen; purple tiles would be the path), but I’m going to have to improve the system further if I don’t want it to grind the game to a hault.

It’d be great if there were two search modes – an accurate mode, which found a path on the actual map the player sees, and a simplified mode, which was essentially finding a path on a representation of the map on a smaller grid (because there’s worse performance for larger search areas). In fact, I already have a smaller representation of the grid coded up in memory. The game was initially more akin to a clone of the game Civilization II, and looked like this zoomed out:

I described in this post how I went about taking the old maps, which were about 5,000 tiles in total, and transforming them into the new maps, which are 84,000 tiles in total. It should be pretty trivial to keep the old map in memory, perform our pathfinding on it, and then convert the tiles into tiles on the larger map. This would be useful for if a unit needs to plot a path far from where it’s currently located.

This would even allow me to precompute and/or cache some common paths, which is the approach I took in the game Sins of a Hex Empire. There I stored the path to every possible location you could travel to from any given hex. Generating a map took slightly longer because it had to precompute all the paths, but it allowed me to have a better AI since I could brute force more stuff, and it had no wait time between turns.

You can see this working here. It shows the number of turns it would take from the topleft most tile to reach any other given tile. This was done and saved for each tile. Then to find a path, you’d just start at the goal and travel backwards, with the next tile being the lowest number. Truth be told it was overkill for the game, but I think it might be worthwhile for IAEINW. It wouldn’t be a good idea or perhaps even feasible to do with 84,000 tiles, but it might be reasonable for the simplified map.

That’s all for now. Hopefully I’ll have some actual progress to report soon.

Copyright © - Daniel J. Petersen