Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Pillbo]

This is a suggestion about this quote from the latest FoTF

4. At some point, will siegers/other creatures no longer have omniscience about which way to go into a fortress and actually potentially even wander into dead ends if someone say, builds a maze?

4. To some extent we're going to try this, or something related to it, in terms of thinking about death heavy-areas at the very least.  Taking away omniscience means storing knowledge though, in some form, and for maps this gets expensive and/or slow, rapidly.

As an alternative to having invaders keep an active memory of where they've been and where to go you could do something similar to the pheromone trails ants lay down to find their way into a fortress. Ants will lay down scent trails as the travel around that others can follow, when they find something useful, like a path into the fort, they return to the group laying down a second type of scent trail inviting others to follow.  The more they use the same path the stronger it gets while fruitless paths disappear over time.

I think doing something like this would have a pretty good effect of getting siegers to explore instead of directly pathing into any opening, and simulating the sharing of the knowledge they learn while exploring. Combine that with emotional responses like fear of a pile of their brethren's corpses and I think you can make a pretty 'inexpensive' simulation of memory for a group. It could rely on a type of invisible contamination/splatter that siegers can use that don't have any other effect. For example if every goblin that enters a trap maze never returns that path is going to be less desirable, just like real invaders would assume if the scouts going in some direction never return.

Basically Ant Colony Optimization

[NW_Kohaku]

While this is different in that it is about invaders rather than general pathfinding, I think the same problems that apply to general pathfinding apply to invader pathfinding, if not more so.

Before getting into it, there's been a LOT of discussion on pathfinding over the years, and it's gotten pretty detailed, so there's going to be a LOT of repeated discussions.  Here's your customary few threads from a cursory search that specifically talk about Ant Colony Optimization, and discussions of its limitations, although again, this is mostly for general-use.
www.bay12forums.com/smf/index.php?topic=43265.0
www.bay12forums.com/smf/index.php?topic=76278.0
www.bay12forums.com/smf/index.php?topic=24615.msg277864#msg277864
www.bay12forums.com/smf/index.php?topic=28051.msg350817#msg350817
www.bay12forums.com/smf/index.php?topic=74846.msg1875017#msg1875017

OK, so, first off, the most immediately obvious problem with ant colony pathfinding is that ants don't know where their destination is until an ant finds food (or danger to warn the other ants about).  Yes, what you're trying to simulate is that goblin siegers don't know where the dining hall is, so they have to search for it once they get into your fort... the problem is that if you're not guiding them by anything but ant trails, they're not going to start searching for a path inside your fort, they're going to start searching - completely blindly - as soon as they get on the map.  This means wandering completely randomly until Brownian Motion manages to make them hit the right path.

But hey, that sounds like I'm being uncharitable and nitpicky because there's a solution that seems obvious.  The easiest, most obvious way to avoid this problem would be to say "OK, you use A* pathfinding to find a path to the dining hall until you get inside the fortress, then the pathfinding turns off, and THEN they ant colony pathfind."  Except... where does "inside" the fortress begin?  Remember, YOU see the intentionality you put behind things like walls and drawbridges and moats with alligators in them, but the computer only sees tiles with walls and tiles that are open space.  If you make it so that anything "underground" is "inside", then it means you invalidate any maze on the surface or an all-surface fortress, for that matter.  It encourages making a simple hallway underground all the way to the edge of the map to ensure that all entrances are through tons of "underground" that aren't really "part of the fortress".  It encourages really gamey strategies, rather than having a system where scouting would be logical.

But OK, OK, we don't really want our gobbos blindly stumbling around like they're actually blind, right?  The realistic behavior we want is to have gobbos look at a "fortress" (which may be little more than a hatch on the side of a hill, or a small pit leading to a door in an otherwise totally natural landscape), and find whatever within line-of-sight looks like it might be a possible path to the rest of the fortress, or at least, try to search and fill out their own mental maps.  The way to do this isn't ant trails, which requires having already stumbled across the path several times, but something like a vector-based pathfinding system, where gobbos will look at what they have unobstructed line-of-sight to, then make a choice about which parts of the map they're most curious about.  Ideally, this would also include a weighting towards being curious about what's behind a door more than what's on the other side of that tree.  This is getting really complicated, but what's important is that this ideal behavior is going to be a radically different pathfinding system from ant colony optimization.  The "scouts didn't return" thing you mention in the OP just isn't an ant trail, as an ant trail only gets laid by the ant that comes back.  If you want a commander that sends out scouts, and bases their decisions on what scouts say when they come back, you're talking about a wholly different kind of AI script.

But there's a larger problem with how efficient this ant colony pathfinding will be.  The thing is, ant colony optimization relies upon multiple iterations to finally create a high probability path.  Basically, it only makes sense when you have ants find the food and make multiple trips back and forth.  This is not at all analogous to the DF situation.  The invaders only need to find the "food" (reach the dining hall) once, then they've killed all the dwarves.  Any invasion that fails will at best leave behind the "panic"/"danger" pheromone.  This is basically what Toady has already planned doing with A* with invaders that avoid pathing through tiles (adding pathing cost) when there are invader deaths in those tiles, minus the blindly stumbling around part, but more complicated and costly.  Without having a goal to reach at all, then gobbos are going to be functionally performing a flood fill pathfinding, just in real time instead of all at once.

And this is where there's another big problem: Again, there's no "food" to show a correct path, just at most "danger".  So if a gobbo finds the right path that leads to more of the fortress, how do the other gobbos know?  In fact, how does the gobbo that found the right path know themselves?  They don't know where their goal is until they found it, that's the point, so if they manage to find a good path, they have no means of recognizing one unless they actually get to the dining hall and return, leaving a "food" trail that other gobbos can follow.  This is, again, moot, because the player's already lost if the gobbo isn't dead by the time it reaches the dining hall, can dance around, then find a path back that other gobbos can follow.  This basically means that you're designing a system where gobbos wander around randomly, then bumble into your defenses one at a time without communicating or coordinating - sounds like a really easy siege to defeat!

And that crashes into the next problem:  The only pheromone that will be left is "danger".  Especially if gobbos are trickling towards the fort's defenses one at a time, what are you going to do as a player to stop those goblins?  You're going to put your military in the way, right?  That means that the "right" path is the one that has the dangerous military dwarves in it.  Meaning that the right path is going to be the one with the biggest concentration of "danger" pheromone, the one that warns the other gobbos that this is the wrong path and that they should stay away. 

Also, if you wanted to have a really realistic lost gobbos in your fortress, then they shouldn't take back to their civilization any warnings of danger if those gobbos were killed instead of escaping.  Even if one gobbo who got lost winds up running away when everyone else died, they shouldn't know what the gobbo in the gauntlet or the magma shower or the FB pit saw before they died.  This means you're going to need to save several different maps, with an invader civ map of your fort that updates only with what survivors saw.  If nothing is updated, the map is a blank slate every time, meaning that everything has to be learned entirely from scratch every time, meaning it's back to bumbling around in the woods lost.  That means you're updating and saving multiple connectivity maps for the fortress all at once.

I should point out that connectivity maps create noticeable spikes in lag when updated.  Just having an atom smasher in my fort, where a drawbridge keeps pushing for an update of the connectivity map (even in a sealed area that shouldn't have a connection to anything else) creates a massive lag spike.  These maps can involve a lot of data, so even a "all gobbos see what all other gobbos see" system where each civilization only has one map system is going to cause some delays.

Oh, but don't worry, it still gets worse!  See, one of the problems with a lot of pathfinding systems that are more efficient (and especially ant colony pathfinding) is that they require a map that is consistent.  Dwarf Fortress does not have a consistent map.  Dwarf Fortress is a game where players can slam shut drawbridges and close off once-valid paths, while lowering drawbridges that were up, creating a new valid path where once it was marked as a dead end.  This is just drawbridges, at that, not even counting all the construction dwarves can do between the time of one siege to the next!  Everything that was recorded about a fortress has to be assumed to be wrong until proven right when the next invader comes.  That utterly destroys the primary thing an ant trail is useful for - gradually learning an optimal path through an unchanging terrain over time.

Basically, the idea of a blind invader is an interesting mechanic, but ant colony pathfinding just doesn't actually help you achieve it, as its primary benefits are all useless in the particular circumstances Dwarf Fortress would put invaders into.  The part you actually want to focus upon is the random searching part that comes before an ant can leave a trail, and that's necessarily going to have nothing to do with the ant trails.