Crossposted from my site
This post is a little more technical, but hopefully someone out there will find it useful if they're wondering how to face a similar issue.
Possession 2 features two basic types of creature behavior, dumb and smart (though there are a lot of complications that can go into them to make them act differently within the two categories, as touched on in a previous post
Dumb creatures are fairly simple, as you might expect. If they see an enemy, they move towards them in a straight line, if they can. If there are any obstacles blocking the way, they go around them using basic pathfinding. They will move through dangers that don't block movement (fire, lava, poison gas) without caring.
Intelligent creatures, like dumb ones, move in a straight line to their target if possible. The difference is that they pay attention to whether or not there are hazards in the way. Now, just avoiding hazards would be easy enough, I'd just have to set tiles with dangers on them to be "impassable" on their pathfinder, and they'd path around them like other obstacles. But I don't want them to avoid dangers all
the time. If it's impossible (or extremely impractical) for them to move around a danger to get to their target, they should be able to go through them.
What I ended up doing was implementing what this article calls "Djikstra maps."
Basically, the way it works, is that it takes a section of the map, and creates a grid on it. Each square on the grid is set to 10, except impassible squares like walls, which are ignored, and "target" squares (usually enemies), which are set to 0.
(In this situation, the drunk tourist would actually just move in a semi-straight line -- depending on how drunk he is -- towards the ghost and wouldn't bother making a map, but I'm doing it as an easy example.)
Then, it loops through all the tiles, until each tile is one greater than the lowest tile it borders (ie all the tiles next to the ghost are 1, all the ones next to those are 2...)
(Just realized I made a mistake, the tile in the upper-left should be 4, not 3.)
Then, the creature picks the tile it's touching with the lowest number (randomly choosing between them if there's a few it's touching).
This method is also used for creatures running away. Instead, they just pick the highest
number they're touching. Fo example, imagine the image above stretches to the right a little. All those tiles to the right would be 4, and the drunk tourist would move to them if it was running away.
Things get a little
more complicated if there are hazards involved. In that case, the hazard adds a number to the tile's value, depending on how dangerous the hazard itself is (which is set on a hazard-by-hazard basis when I make them). For example, the hazard value of fire is 10. Let's set a few fires next to the ghost:
Those tiles, which would normally be 1, are now 11. Notice that this changes the values of the tiles next to them, too. The tourist now has fewer options to get to the ghost, plus its route is going to be a little longer.
It's all well and good to draw numbers on pictures, but how does it work in action? Let's take a look at another situation, and do the numbers by hand to see where the drunk adventurer should walk, sans any drunken stumbles into the fire (these pictures are all from the tavern level, and if you can't tell, there's a lot of drinking going on there):
And what path does it take in the game?
As I mentioned before, different hazards have different danger values. Fire's is 10, which means it's super dangerous, but what if it was only 1?
Now, it's possible the drunk adventurer will still take the same path...its values haven't changed. But, it could step into one of the fires marked 6, because they have the same value as the empty tile, and the creature randomly chooses between equal values. This would actually save it some time, but it doesn't actually know that because it only looks at the tiles next to it, it doesn't actually plan the whole path in advance (it only looks
smart, it's not actually that smart).
Last theoretical situation in this longer-than-normal post...what if there's a fire in the doorway next to the ghost (setting fires back to 10)?
The numbers are all higher, but it'll follow the same path as originally, even stepping into the fire at the end. This is what I was talking about way back in the beginning of the post...if they just can't avoid it, they will still walk through hazards.
And actually, right now, once it is next to the ghost, it won't even care that it's getting burned. It'll try to attack the ghost because attacking things has a higher priority than moving. I should probably change that if you're in a dangerous place like the middle of a raging inferno.