Show Posts
1
Programming / monsters surround player tech demo
« on: February 05, 2013, 09:45:36 AM »
I wrote a monster decision-making (monster AI) tech demo:
http://www.interq.or.jp/libra/oohara/surround/index.html
Only the source code is available. Compile it with gcc and ncurses.
Monsters usually chase the player by following the shortest path
to the current position of the player. If only one monster can be
in a grid, this is not the best. To take advantage of numbers,
the destination of monsters should be the adjacent grids of
the player character, not the current position.
The tech demo assumes that:
+ the monsters want to kill the player at any cost
+ hitting the player is always a good thing
+ there is no ranged attack; the only attack is a bump into something
+ the monsters know the map of the dungeon
+ the monsters always know where the player is
+ the monsters know what others are doing
The decision-making code is called just after the player action is done.
It uses the current best action of monsters to improve the decision of
other monsters.
If a monster is adjacent to the player, it attacks the player.
Otherwise, it decides its next action in 3 steps:
(1) see where it wants to go and find the path
(2) make sure monsters near the player are not blocked
(3) cancel the move if a monster near the player is alone
Path-finding in the first step is done with a Dijkstra map.
The first step uses 9 Dijkstra maps. One map is for a direct chase:
+ the destination is the current position of the player
+ only the wall grids are considered blocked
The other maps are for an indirect chase:
+ the destination is one of the 8 adjacent grids of the player
+ the adjacent grids other than the destination are considered blocked
+ grids with a monster are considered blocked
A monster chooses a Dijkstra map with a non-wall destination and moves to
the best grid according to the map.
The second and third steps handle monsters which engage this turn.
Engaging means that a monster which is not adjacent to the player
gets adjacent. In the second step, each monster counts the number of
the adjacent grids of the player which are also adjacent to the monster.
This is the number of choices of the monster in this turn. The monster
with least choices decides the action first. The third step cancels
engaging if only one monster is adjacent to the player after the move.
http://www.interq.or.jp/libra/oohara/surround/index.html
Only the source code is available. Compile it with gcc and ncurses.
Monsters usually chase the player by following the shortest path
to the current position of the player. If only one monster can be
in a grid, this is not the best. To take advantage of numbers,
the destination of monsters should be the adjacent grids of
the player character, not the current position.
The tech demo assumes that:
+ the monsters want to kill the player at any cost
+ hitting the player is always a good thing
+ there is no ranged attack; the only attack is a bump into something
+ the monsters know the map of the dungeon
+ the monsters always know where the player is
+ the monsters know what others are doing
The decision-making code is called just after the player action is done.
It uses the current best action of monsters to improve the decision of
other monsters.
If a monster is adjacent to the player, it attacks the player.
Otherwise, it decides its next action in 3 steps:
(1) see where it wants to go and find the path
(2) make sure monsters near the player are not blocked
(3) cancel the move if a monster near the player is alone
Path-finding in the first step is done with a Dijkstra map.
The first step uses 9 Dijkstra maps. One map is for a direct chase:
+ the destination is the current position of the player
+ only the wall grids are considered blocked
The other maps are for an indirect chase:
+ the destination is one of the 8 adjacent grids of the player
+ the adjacent grids other than the destination are considered blocked
+ grids with a monster are considered blocked
A monster chooses a Dijkstra map with a non-wall destination and moves to
the best grid according to the map.
The second and third steps handle monsters which engage this turn.
Engaging means that a monster which is not adjacent to the player
gets adjacent. In the second step, each monster counts the number of
the adjacent grids of the player which are also adjacent to the monster.
This is the number of choices of the monster in this turn. The monster
with least choices decides the action first. The third step cancels
engaging if only one monster is adjacent to the player after the move.
).