efficiency of dragon's teeth on biters

[sthalik]

Hey,

The pathfinding issues aren't directly addressable through Lua without the heavy cost of doing pathfinding in a scripting language. Please discuss how it affect you in your playthroughs and whether you observe the same problems.

There are wall layouts having a high degree of confusing biter pathfinding using either labyrinths or dragon's teeth. The primary issue is that biters attempt to cross the overlong path at all (unless their collision boxes are too big) rather than razing it. The secondary issue is that multiple biters confuse each other when they're blocking each other's paths. You can see the same effect in e.g. Baldur's Gate 2 when traversing a tight corridor with the party.

The secondary issue is most evident with dragon's teeth. The path isn't overly long then but they confuse themselves through pathfinding. There's a solution used in the game industry - change the pathfinding to a formula where units blocking the path are neighbors but with higher weight:

Let the biter having its path computed have stationary time "a" in suitable units.
Let the blocking biter have its stationary time be "b".

Compute the path ignoring same faction's collision, but having the distance's weight for faction-blocked tiles multiplied by "(C)max(a, b) + M" with fine-tuning.
If the blocked path has the lowest cost (or there's no actually-passable path), wait there, attacking the nearest enemy object in the pollutant's direction in melee/ranged. Recompute cost soon, especially if other units move.

The primary issue is most evident with labyrinth wall design. It's ok to assign an impassable wall tile a cost as well, rather than treating it as a non-neighbor in A*/Dijkstra. Assign a cost that's lower than now, encouraging biters to kill walls. Maybe compare Bresenham distance to full pathfinding. Assume anything longer than, say, 1.5, is a labyrinth and kill the walls. Progressively destroying the labyrinth's walls is more severe than traversing it and dying.

Another solution for the primary issue is to pathfind with an enlarged collision box. If sufficiently enlarged when moving toward target (say even 4x), will treat terrain as impassable and smash a simple path.

So here are wall designs:

Code: Select all

Legend:
T - turret
U - turret "targeted" by biters (who die before reaching it)
| - wall
* - wall targeted by biters

  === NAIVE WALL ===

            T |||*
            T |||*
              ||||
 TASTY        ||||
FACTORY       ||||
              ||||
            T |||*
            T |||*

  === LABYRINTH ===

              | | |
            U |   |
            U | | | |
              | | | |
 TASTY        | |   |
FACTORY         | | |
              | | | |
            U | | |
            U |   |
              | | |

  === DRAGON'S TEETH ===


            U | | |   |   |
            U   |   |   |   |
              |   |   |   |
 TASTY          |   |   |   |
FACTORY       |   |   |   |
                |   |   |   |
            U |   |   |   |
            U | | | |   |   |

[Hedning1390]

Why do you want biters to have better pathfinding?

[sthalik]

Why do you want biters to have better pathfinding?

To serve their purpose.

[Hannu]

Why do you want biters to have better pathfinding?

It would be more interesting and give more natural and realistic feeling if there were smaller number of more naturally behaving enemies in video games instead of insane number of cheaply programmed simple enemies, which just run straight until they die. Modern computers would certainly give many other possibilities than just increasing number of enemies like in 80's.

[Aeternus]

Simpler pathfinding could also solve it.
When path is blocked - If blocking object is not owned by the biter force/faction - Start chewing through. Trees, rocks, walls, nuclear reactors at 900 degees... Biters do what biters do best.

[mrvn]

Why not simply give tiles a cost proportional to the time it takes to cross it? So paved road is cheap, desert is moderate and tiles with walls on it are rather expensive. The path finding will prefer to use the road for quickest travel. But if chewing through the wall is quicker than walking the maze then by all means chew.

Note: Make chewing walls cheaper than it actually is time wise to include the furstration factor. Yet another wall in my path *grrr*.

[sthalik]

Why not simply give tiles a cost proportional to the time it takes to cross it? So paved road is cheap, desert is moderate and tiles with walls on it are rather expensive. The path finding will prefer to use the road for quickest travel. But if chewing through the wall is quicker than walking the maze then by all means chew.

This is how pathfinding is done. The "cost" of a single node is how long it takes to traverse it. Except that when units of the same faction run into one dragon's teeth area, they block each other. The blocked one then recomputes a very long path and suddenly goes into the other direction. Thus they never effectively go for the turrets.

In Baldur's Gate 2, having a party member go through a tight corridor makes the one that gets blocked (think boots of haste, being faster to traverse it) go through an absurdly long path across the whole map, separating from the party. They fixed the pathfinding as I explained in the OP for the third-party "Enhanced Edition". It was one of these code bugs that wasn't possible to fix by modders without access to the source code.

Note: Make chewing walls cheaper than it actually is time wise to include the furstration factor. Yet another wall in my path *grrr*.

Dragon's teeth have no downsides for the player and work "too" effectively. There shouldn't be pathfinding weaknesses to exploit. If biters have to be dumber, have it programmed explicitly rather than relying on an inadequate pathfinding implementation.

[mrvn]

Why not simply give tiles a cost proportional to the time it takes to cross it? So paved road is cheap, desert is moderate and tiles with walls on it are rather expensive. The path finding will prefer to use the road for quickest travel. But if chewing through the wall is quicker than walking the maze then by all means chew.

This is how pathfinding is done. The "cost" of a single node is how long it takes to traverse it. Except that when units of the same faction run into one dragon's teeth area, they block each other. The blocked one then recomputes a very long path and suddenly goes into the other direction. Thus they never effectively go for the turrets.

Except that walls are uncrossable so normaly path finding will path around them. All the descriptions so far said the alien would attack when it can't find a path. You made sure it can find one even if it is long. If instead you simply make walls expensive to cross (not too expensive, just more expensive than a short detour) the amount of going around becomes limited. You can't make your maze too complex or chewing through a wall will be a shortcut through your maze.

Next units block paths. So all the short ways around an obstacle are blocked. Checking through a wall becomes even more attractive comparatively. The first bitter will enter the maze, the second bitter will walk the other way to enter the maze another way. Maybe the 3rd and 4th bitter will too. The 5th bitter than would need such a long detour that chewing the wall is more attractive.

Note: I agree with you that units of the same force should not block a path but should cause an extra cost. Aliens should take a small detour around other aliens but not too far. At some point its better to just wait for the way to clear or chew some walls. To prevent bitters being stuck behind spitters there is a little trick one can use. Allow 2 units to swap places if they aren't (want to) going in the same direction.

[HurkWurk]

its been my experience that dragons teeth work as they should.
biters either attempt to path through, or they start chewing. in both cases, they are slowed down while my guns do their jobs.
i use bob's enemies, so maybe he adjusts things, but frankly, I dont see any issues with the current way the waves attack.

[mrvn]

its been my experience that dragons teeth work as they should.
biters either attempt to path through, or they start chewing. in both cases, they are slowed down while my guns do their jobs.
i use bob's enemies, so maybe he adjusts things, but frankly, I dont see any issues with the current way the waves attack.

Odd. they shouldn't be chewing currently.

[sthalik]

This is how pathfinding is done. The "cost" of a single node is how long it takes to traverse it. Except that when units of the same faction run into one dragon's teeth area, they block each other. The blocked one then recomputes a very long path and suddenly goes into the other direction. Thus they never effectively go for the turrets.

Except that walls are uncrossable so normaly path finding will path around them. All the descriptions so far said the alien would attack when it can't find a path. You made sure it can find one even if it is long. If instead you simply make walls expensive to cross (not too expensive, just more expensive than a short detour) the amount of going around becomes limited. You can't make your maze too complex or chewing through a wall will be a shortcut through your maze.

See the dragon's teeth structure. It has no labyrithine structure but takes advantage of the pathfinding. I wasn't saying in the OP that chewing through dragon's teeth in all circumstances is good, but rather than shuffling back and forth in arbitrary directions, wait for units that are already chewing in case the path is the same. This is the frequent scenario with "optimal" pathfinding:

- Unit takes a path through dragon's teeth
- Other unit takes the same path and goes there faster
- The original unit takes some other "optimal" path, spending seconds getting there
- That path is now blocked too, the unit spends more seconds trying to get anywhere

I said "chew in place while waiting" because it's more optimal than just waiting, and opens up new paths. It's optional to chew in place, the important bit is waiting.

See the same behavior in Starcraft: Brood War where a blocked path causes units to go-around on what the player considers nonsensical detour. Unit group is meant to stay together in SC:BW, since their sole amount is a force multiplier. Similarly in BG2 a mage isn't meant to expose themselves to random enemy groups.

Next units block paths. So all the short ways around an obstacle are blocked. Checking through a wall becomes even more attractive comparatively. The first bitter will enter the maze, the second bitter will walk the other way to enter the maze another way. Maybe the 3rd and 4th bitter will too. The 5th bitter than would need such a long detour that chewing the wall is more attractive.

The 5th biter should wait at the blocking unit. See the original post for the dragon's teeth structure.

1. The detouring unit will take a new path until it's blocked, not recomputing it unless it's blocked also. Pathfinding is actually an expensive operation in terms of CPU time. See amortized time for Dijkstra and A-star.
2. In the dragon's teeth layout it's more beneficial to wait since each biter moving through opens up two or more new paths when crossing.

Please see how naive group pathfinding works, and how nonsensical it is. It may not seem so from a raw description.

Note: I agree with you that units of the same force should not block a path but should cause an extra cost. Aliens should take a small detour around other aliens but not too far. At some point its better to just wait for the way to clear or chew some walls. To prevent bitters being stuck behind spitters there is a little trick one can use. Allow 2 units to swap places if they aren't (want to) going in the same direction.

Adding an extra cost for moving away won't work since the blocked tile isn't even considered, it's not marked as a "neighbor" in the pathfinding graph[1]. Maybe rather add a cooldown before recomputing when blocked by same force's unit, say, 1.5 seconds. And eat stuff within melee range for that cooldown too :) This is very simple compared to a fully-fledged solution.

Having two units swap places would just make them swap places in a loop until either is killed. This is called a "livelock" in programmer parlance. OTOH having them overlap at times I'd consider bad taste.

See this video for a pathfinding demo for one unit - https://youtu.be/cSxnOm5aceA?t=42. Then consider a tile is blocked and the unit has recompute, then go all the way round.

[1] non-neighbor tile is like water, can't go through it.

[sthalik]

To elaborate on pathfinding obstruction effects - see this video with Starcraft pathfinding when other units are ordered to "hold position" over the entry points. Now, imagine the units turned due to other moving units, not just having all paths obstructed. In this case, units only stop if they're close to the center position. This is to avoid units twitching around as a group when moved somewhere. That Starcraft pathfinding is even more braindead than a naive implementation, units make useless walk-abouts when it's obvious the target can't be reached at all.

Here's the video. Sorry for ineptitude with recording - https://www.youtube.com/watch?v=FlVULp_oL7s

[nevniv]

I'm not against any improvements to pathfinding, but do you have any examples of where pathfinding is an issue that doesn't involve cheesy dragon's teeth?

[sthalik]

I'm not against any improvements to pathfinding, but do you have any examples of where pathfinding is an issue that doesn't involve cheesy dragon's teeth?

Traversing labyrinths as well. These are all edge cases and not normal cases for pathfinding. It's just that in these edge cases the current pathfinding scheme breaks down. I'm considering increasing all of biters' hitboxes several times, i.e. unable to traverse dragon's teeth without destroying them, and unable to traverse 1- or 2-spacing labyrinths without tearing them down. It should work with big biters and above. At the same time, make small biters' hitboxes very small to avoid pathfinding problems with dragon teeth.

Pathfinding is easy to get right in principle, but avoiding suboptimal behavior with these cheesy structures is another thing really.

By making the hitboxes small I was able to make small biters traverse dragon's teeth with ease. The labyrinths are still worrisome but big biters make short work of walls.

Consider, for small/medium and big/behemoth biters, respectively:

Code: Select all

local sz = 1.65
local sz2 = .16

--[[ original values:
  small - .4
  medium - .6
  big, behemoth: .8
]]

Labyrinths are more costly to produce so having small/medium biters getting trapped in them may not be that bad. Also they're bad at destroying walls regardless, so it's not a great loss.

I'd rather program this myself but from Lua there's no API for it. Also without LuaJIT it's bound to be excruciatingly slow regardless. I'm settling for "data-final-fixes".

With similar settings as these for small/medium biters, I saw them traverse dragon's teeth almost as easily as a player would do.

[Veden]

Have you tried the Rampant Mod (https://mods.factorio.com/mod/Rampant)?

The mod uses potential fields instead of A* or Dijkstra, which allows for a manageable dynamic paths within the game.

Also the size of the biters and spitters has been reduced to allow for the units to slide by each other for better swarming behavior.

Unit groups should attack defenses like dragons teeth without trying to cram through them as well.

[sthalik]

Does the Lua game API allow for overriding pathfinding? There's API for ordering attacks at specific coordinates that much I know.

[Veden]

No, I build an in memory representation of the map and perform pathfinding resolution at the level of chunks for move/attack commands.

[Frightning]

I wonder if the devs could implement something like SC2's pathfinding (greatly improved compared to SC:BW via the use of fluid-flow algorithms if memory serves). Same techniques have been used in other media and other games (SupCom2 comes to mind) for the same reason.

[BlakeMW]

I use another exploity layout specifically for maximizing flame turrets, which looks something like this:


The idea is to make incineration a non-frustrating experience for biters, they simply queue up in an orderly fashion and move forward into the fire falling behind the lead biter. Also since biters usually run in 5-10 abreast in groups, but have to go single-file into the fire-tube, it gives longer for the defenses to do their work. The biters which can't fit down the firetube typically run back and forth along the walls. The tube always looks open enough that they never get frustrated and I find this layout is less frustrating than traditional dragon teeth (i.e. they bite the walls less, and it takes them longer to start biting), it comes extremely close to being zero-maintenance.

Now the question is: Should this be considered an exploit of game mechanics, or a clever use of game mechanics? The biters are kind of meant to be dumb as bricks, but then again if they are dumb as bricks they should be happy just biting bricks. Overall I wouldn't find it objectional if biters just starting chewing at the slightest frustration, though in this case it would be nice to have a higher tier wall which stands up better to Big/Behemoth bites and a way to make construction bots wait until things cool down.

[nevniv]

I'd say you are exploiting the game's mechanics but it is not an exploit (flaw in code). You're just playing the meta.

Personally I just make a ridiculously long double concrete wall with lasers and the strategies in this thread never crossed my mind. Maybe that's why I'm bad at the tower defense genre.