Buy It
It's out.
Latest Trailer
Throw a wrench, change the galaxy.
Screenshots
Mostly nebulae.
Platforms
Windows, dunno about others
Team
Design, Code, Writing
Art
Code
John Winder
Music
Chris Harvey
Site
Tom Francis
John Roberts
Pathfinding In Heat Signature’s Randomised, Modularly Destructible Spaceships
Updated! see bottom of post.
Heat Signature is a game about randomised space ships that you can sneak aboard. These ships have a randomly generated interior of connected rooms and corridors, and crew that patrol those rooms.
Right now, there’s no pathfinding: the crew roam randomly. At some point, though, you’ll be able to set off alarms or cause other disturbances that the crew should run to. So the problem is: how do find a route to that room? Specifically, how do they find the shortest route to that room?
I could cheat a bit: right now each row of rooms in a ship is always internally connected, and each has just one door to the next row. But I might change that layout logic, and as I’ve been planning the features for Heat Signature, I’ve noticed something interesting: a lot of the problems I’ll need to solve utlimately boil down to: “Is this module connected to that one?” and “If so, what’s the shortest route?”
Crew pathfinding is one. Player pathfinding is another, if I keep the current controls. But also, when a ship is hit by a missile, the module that got hit is destroyed. If you blow up enough modules to cut a ship in half, it ought to break apart. How do we tell when that should happen, and which modules should belong to which half? Well, we need to know “Is this module connected to that one?”
Fourthly, and this is just a pipe dream, but if it’s not too hard I would love to have vacuum suck you out into space. So when that module gets destroyed, it takes a second for the doors that were leading to it to seal, and everything would be sucked towards it in that time. To figure out what gets sucked and in which direction, we’d need to know: “Is this module connected to that one?” and “If so, what’s the shortest route?”
In programming, you’re always hitting challenges other people have already solved. The best policy is to do your research, find out what the best solution out there is, and adapt it to you purposes. But I hate research, and I love figuring things out, so I have a different policy: try to figure it out for yourself. If you can’t, or your solution seems insanely hard to implement, then look it up.
So I haven’t looked up how you do pathfinding – I’m going to try my own way first. And since it’s a big subject and I’m blundering through it in my head, I thought I’d write out the approach I’m going to try before I actually try it, partly to make sure the logic is sound before I do the legwork of implementing it. So here’s my plan:
Pathfinding By Induction
In maths, there’s a very useful process called induction: if you want to solve a problem for all numbers, start by solving it for ‘1’, then use that result for ‘2’, and so on. Algorithmically finding the shortest route between two distant points in a selectively blocked grid seems daunting to me, so I think I’ll start with the case I can solve and work from there. If two modules are connected by a door, I can definitely tell you the shortest route between them.
It would work like this:
Every module is assigned a number, from 1 to however many modules there are on the ship.
We want to give every module two lists: one is how far it is to each other module on the ship, and the other is which way you should head if you’re going to that module.
So if the Cockpit is module 1, module 8’s lists will hopefully end up including something like:
- DistanceTo[1] = 5 modules
- NextStepTo[1] = go to Module[7]
But we don’t know that yet. So when the ship is created, all these distances are set to a big number (ModuleCount) – no module knows of a good route to any other one yet.
Then we go through the modules one by one.
For each module, we check to see if it has a door to any of its neighbours.
For each of its connected neighbours, we say:
- The distance to that neighbouring module from here is 1 (DistanceTo[n] = 1)
- To get to this module, just head straight to it (NextStepTo[n] = Module[n])
These ones are easy! But obviously we can’t stop there. So we also look at the neighbouring module’s list of distances to each other module in the ship, and ask:
- Is your best known distance to that module much (2) shorter than ours?
- If so, we can find a better route to that module by going through you!
- Our distance to that module is now your distance + 1: we take one step to get to you, then use your route (DistanceTo[d] = Module[n].DistanceTo[d] + 1)
- So our NextStepTo that module is you (NextStepTo[d] = Module[n])
So that’ll get us some routes to modules that aren’t our neighbours, but obviously it won’t get them all – not on first run. When we run this for the first module in the ship, none of the other modules have routes to anywhere, so it’ll only know about its neighbours.
But this process is sound: it’ll never replace a good route with a worse one, and each time you run it it’ll find efficient routes to more and more distant modules, until all the lists are optimal.
How many times do we have to run it for that?
Well, we can stop running it when the routes aren’t changing anymore – if none of them change on one run, they also won’t change on the next one, so the process is finished.
Why This Method?
For a single pathfinding operation, this method is probably super inefficient: it involves a lot of nested loops, so the total number of operations it’ll do is very high. I’m trying it because:
a) I’m too dumb to see how to optimise it, and
b) it doesn’t really matter if it’s a bit slow, because it doesn’t need to run at all for people to navigate. Every room has a static list that tells everyone where to go next without performing any actual calculations. So you could have thousands of crew and thousands of modules and still spend zero cycles on pathfinding. It only needs to recalculate when the ship physically changes shape, which happens much more rarely.
It’s probably still a dumb method and I’m sure many of you will point out problems or better ways of doing it – please do! But I’m interested to give it a go and see how it works. I might even put in some visualisation stuff so I can see it working, and the paths it creates.
Update
It worked! Here’s a shot where every room is showing the shortest route to the player from there (click for big):
Next step is to check it works when a ship is damaged – maybe I could also make crew run to the point of impact to give it a test run, too. Might do a video once everything’s all working together – I’ve also added heat seeking missiles and infighting between ships since the last one.
More Heat Signature
Micael:
You will want to take a look at A*, it’s a very simple algorithm that finds the shortest path between 2 points, and does so by attributing costs of movement to each nearby square (then selecting the next square and repeating said process), you can read this http://www.policyalmanac.org/games/aStarTutorial.htm it is a very clear example of what A* is, and how to implement it, it is pretty much THE algorithm that most node base pathfinding systems use. As for speed that page also links to another page about binary threes which help speed things up significantly (in exchange for memory cost), but honestly unless you are going to make ships that are a lot (and I do mean a lot) larger than the ones you have shown, there is 0 need for it, and yeah you will have nested for loops, it’s normal (even if ugly).
Also I forgot are you using unity for this or gamemaker, if you’re using unity you should take a look at something called linq for c# which is functional programming language feature that would make your code a lot more readable (also you have A* pathfinding already done on the asset store), since you would get to avoid all those for loops.
Aldo:
Why not use old-fashioned on demand A*, with a manhattan-distance based heuristic? It should be pretty fast (it’s a very well established approach), surprisingly easy (I mean, I managed to do it thanks to some decent tutorials), and it’ll allow aspects of the layout to be changed at will (so you can have tactics like sealing doors etc) to block the AI.
If rooms themselves have internal layouts, I’d suggest nesting operations – i.e. one pathfiniding call defines the set of rooms to visit, and a room-specific path is generated from each door-to-door when required. It does sacrifice guaranteed traversability (you don;t know if a room can be traveled through until it’s reached), but should be a bit more optimal.
Micael:
Oh yes forgot to add, if you really really want to take a look into more pathfinding you can check this http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths (completely unnecessary just for fun and added knowledge), it covers pathfinding, optimization, and even some mesh based pathfinding (search recast pathfinding to see what it is).
I’ve wondered about pathfinding on maps like this before when I used to play a text-based game with huge maps built from individual rooms with exits in compass directions. I wanted to code a mapper that could return the shortest route from my room to any other room in the map.
What I figured it would do is run a iterative algorithm seeking out all possible non-intersecting paths (so if a path tries to enter a room that has previously been reached by another path, that path is discarded from the list of paths still being extended). The first pass begins a new path for each direction leading out of the room and each subsequent iteration duplicates every path for every direction leading out of the last room that doesn’t hit a room already visited, saving those paths for the next pass.
Doing this simultaneously from my room and the destination room builds up a list of ‘shortest routes’ that eventually would span all of the map, but the process is complete once a ‘shortest route’ has been calculated from both my room and the destination room to a third room lying between them. The two paths are joined to form the shortest route I originally requested.
In theory, I imagined I would run the algorithm once over the entire map (which would probably take some time) and save the lists of ‘shortest routes’ generated, and then when ever I need to find a shortest route while playing the system would somehow find a complete path using the individual mini-paths as shortcuts.
I never got round to programming it though, since it was too complicated to even map out the world in the first place due to the manyfarious nuances and exceptions in the game I was playing.
I don’t suppose any of that helps you, but it was fun to read your ideas along a similar problem!
Mark:
This is actually a lot like internet traffic routing works. Kudos!
An AI consideration: If a module of a ship is destroyed, should everyone on board instantly know it? Maybe they don’t discover that their shortest route is blocked until they walk it and hit a wall. Unfortunately, this would require a copy of this route model for each individual aboard the ship. On the plus side, you could run the recalculation for each individual in a separate thread so it doesn’t bog down the game loop. If it takes a little while, only that one person will stall, and it’s because that guy is literally trying plan his trip in his head based on the knowledge he has.
Mark: Or you could probably just assume there’s a tannoy system to avoid that :P
Dan:
The algorithm you describe sounds like Bellman-Ford, which is a pretty good choice for what you’re doing. A* is efficient if you have a bunch of actors trying to path to different goal positions. Bellman-Ford gives you paths to a single goal for all actors at the same time, so it’s more efficient if you want everyone to respond to an alarm at the same time. If you run into performance issues, you can always switch to Dijkstra’s algorithm, which does the same thing, but more efficiently.
You can add edge costs to any of these algorithms. Since you’re using a regular grid layout all paths between nodes are the same distance, so this would only be useful if the shortest path is not always the fastest path. For example, if you wanted to add the ability for the player to board up a doorway, and then let the enemies choose whether to break through or go around, you could just increase the cost of the door with the barricade. This is a pretty quick fix, you just add your door cost instead of 1, and then compare your current path to goal cost to (cost of door to neighbor + cost of path from neighbor to goal).
tl;dr You did it right, you can switch to Dijkstra’s algorithm if you have performance problems.
Mark:
William: But– but– artificial stupidity is the *best* mechanic! :)
anothercommenter:
Totally predicted the vacuum thing. :P
Jason L:
I’m guessing hand-implementing algorithms from scratch is a pretty correct philosophy in Gamemaker, but you may not have the same luxury in Unity. With its more flexible language(s) I can imagine writing the correct algorithm or a closely related one, but hitting weird bugs or terrible performance relative to a standard module call.
Micael:
While I can’t speak for the ease of implementation in GameMaker, having implemented it in unity you will find no such problems, as is to be expected since unity uses mono, which is a far more robust solution than anything gamemaker will be able to come up with, after all it’s comparing all the resources that were put into .net (made and used by microsoft), and it’s community, a community whose size is somewhere from gigantic to ginormous, and the mono community (also quite big), to those of GameMaker and it’s community.
Also even discount possible performance benefits of mono vs GameMaker, I suspect implementing a bug free, good performance version of it on C# will be easier than doing it on GameMaker (assuming similar knowledge with both), after all mono already has binary trees in it (even if they are not advertised as such), which already saves you quite a bit of code (the most bug prone part even), and adding to that not only is C# a OO language, but it offers functional programming features (something I doubt gamemakes), which has proven at this point to result in less code, less bugs and better readability.
What can be said about not implementing it when using unity, is that it would be reinventing the wheel (but likely with worse performance), since you already have a ton of A* done in C# that you can freely use, and you also have A* packages on the asset store (with free versions), at are already “battle tested” and ends up just being plug and play.
Max_well:
I’ll just let this here, because it’s for me the ultimate resources on pathfinding algorithm : http://theory.stanford.edu/~amitp/GameProgramming/
Great to see another behind-the-scenes article – loving all of the ideas going into the game.
I added pathfinding to my Heat Signature spaceship generator and also rewrote it for the web. Here it is: http://iceyboard.no-ip.org/hssg/
Improving Heat Signature’s Randomly Generated Ships, Inside And Out - a post on Tom Francis' blog:
[…] is done ahead of time, meaning each ship calculates all possible routes within it every time its floorplan changes. For very large ships, that causes slowdown when a missile takes a chunk out of […]
This isn’t a dumb method at all. A* is probably overkill for a map like this. BTW there’s something similar to your algorithm that precomputes all paths to *all* locations. You can run it at the very beginning, once per ship, and not have to run pathfinding anymore for that ship. See Floyd-Warshall: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Algorithm