Quick and dirty way for typicall monster pathfinding (OR dijkstra variation)

[kuniqs]

I was perusing through Collaborative Diffusion Antiobjects paper which contained simple, yet ingenuous method for simple yet accurate and special-case free monster pathfinding.

Played ADOM? Mons there act simple as expected from a middle-age roguelike. Source code is not released but from experience I can extrapolate the behaviour as:

- Player leaves scent (or turn counter) where he stands
- If monster sees player, it moves closer to him (if path is blocked, sidesteps if it can)
- Else: if feels scent, moves along it
- Else: move randomly

It works pretty well, but what I don't like are all those if, ifs, else, elses scattered around handling any exception possible. Circumventing this with A* and family makes more problems than it solves. Making subtle changes becomes a pain as the game grows.



Here's a solution, modified slightly for a roguelike (examples taken from the paper):

1. Set all passable tiles scent values to 0, impassable tiles as infinite.
2. Start a flood fill from player position setting flooded cells as 1 higher than their parent cells, flooding only passable cells:

Code: [Select]

00000000000000000000000
00000000000000000000000
00000033333330000000000
00000032222230000000000
00000032111230000000000
000000321@1230000000000
00000032111230000000000
00000032222230000000000
00000033333330000000000
00000000000000000000000

empty map flood fill

Code: [Select]

00000000000000000
00555000005550000
0054#######450000
0054321@123450000
0054#######450000
00555000005550000

corridor flood fill
(to understand flood fill, imagine a height map with numbers representing elevation - 0 is sea level. Then imagine monsters as balls placed on hill slopes, rolling to the lowest possible level. There should be zillions of implementations on the Web or Roguebasin)


3. for every monster: check every 8 neighbour tiles, find the one with lowest scent value. If that tile's scent is lower than monster's tile scent, move on that tile. (assuming walking on player's tile is equall to attacking the player). Else: walk randomly.

That's all folks. Almost exact copy of dijkstra map technique, or hill climbing, but it doesn't matter.
The key is to run the flood fill from scratch every time, and treating monster occupied tiles as walls. This prevents jams in corridors and swarms:


Example 1:

Code: [Select]

######
#44566
#3##55
#2##4o
#1##3g
#@1234
######

Going with above algorithm, both orc and goblin will go lower corridor. But..

Code: [Select]

######
#44567
#3##67
#2##77
#1##o8
#@1g99
######
Since goblin is effectively a wall, orc will turn back and pick upper corridor, leaving '@' no chance to escape.


Second example.

Code: [Select]

              ################
                        65433#
              ##############2#
 ####                 6543211#
  oo#         ##############@#   
  oo#                 6543211#
 ####         ##############2#
                        65433#
              ################
Let's assume flood fill reaches those four White Hands by the power of ASCII limitation. First, they will probably cluster in one place..

Code: [Select]

              ################
                        65433#
              ##############2#
 ####        ooo      6543211#
    #        o##############@#   
    #                 6543211#
 ####         ##############2#
                        65433#
              ################

..then get redistributed equally by the scent blocked by other orcs.

Code: [Select]

              ################
                 o      65433#
              ##############2#
 ####               o 6543211#
  oo#         ##############@#   
  oo#                     o11#
 ####         ##############2#
              o         65433#
              ################
Trapping poor hobbit second time.


This can be extended to hunting other monsters by bookkeeping individual scent info. Tad complicated, but doable. Best thing is, it doesn't need any tweaking with existing AI, only that 'move one step towards goal' function - all the work is done by the map. It also has somewhat constant computation time if you limit the amount of flooded tiles.



Problem I noticed with this is when we have a veeeryy long corridor

Code: [Select]

#########################
.........@o.....ooo......
#########################
One orc will combat (or chase) the hobbit while rest will stand slack jawed.
To fix this, we need to modify a bit the scent propagation: instead of treating monster tiles as impassable, we add a constant to the scent value (assuming +5) and use it in flood fill. When we add tiles to flood fill queue, we sort them by scent value, so the scent will be distributed equally.

Code: [Select]

#########################
   22223456                 
   211###56   
   21@o7o66
#########################
the orc on left side of seven (Grunge) has a tile value of 6, on right of seven (Munge) also has 6. Munge will go around the wall to reach @ but..

Code: [Select]

#########################
   22223456789ABCD                 
   211##########CD   
   21@o7o9ABCDEDDD
#########################
..here Munge will keep close to his buddy, since the road is too long to be worth taking it.

[naughty]

Unless I'm missing something this is exactly the Dijkstra map technique Brogue uses.

[Valmond]

It seems actually be the Dijkstra algorithm with a quirk that it stops "flood fill" at a certain depth (the max - scent - distance I guess).

For your single orc chasing you out of a pack, make him give orders to everyone in the nearby to go chase the player
or just make him continue the flood filling from the position he discovered the players scent at
that way the other orcs will too "feel the scent of the player".

[Quendus]

Alternatively: compute the Dijkstra map once every time the player moves or the map is altered, and let all enemies use the same map.