Print

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

[SoulForged]

I'm working on a turn-based roguelike in c, but i'm stuck on the pathfinding; and i would like a little help here:
I have some mosters and a hero, some walls etc. The maps are generated in a semi-random way; and i need some sort of AI to find which way to go to get to the hero in the fastest way. I tried creating differents kind of AI, but most of them aren't applicable in a random map, and the only one AI (i can think of) that works on all kind of maps just tries everything and writes down how many turns would take if the monster choose that way, then decides to go for the shortest..
The problem should be solved but an AI of this kind in a pretty big map, with several different monster would take too long to process.
Can you guys let me see some kind of codes (possibly in c since is the only programming language i'm confident in, or some other language that's pretty similiar to it) that handles the AI for pathfinding?
Thanks in advance.

[Alexhans]

Before looking at anyone's implementation of A* or Dijkstra's algorithm...

You better understand what you want to do...

This should help...
http://www.policyalmanac.org/games/aStarTutorial.htm

[Shades]

Your best best for this, based on what you've said so far, will be to use A*.

It basically does a breadth first search of the map tiles until a solution is found (that isn't accurate but is a simplification).
If you map is static there are ways to speed up the search by removing 'whitespace movement' from the search network (ie only record junctions) but I'll let you research that

Edit: Clearly I type too slow Alexhans

[SoulForged]

Thanks both of you, i'll begin reading and see if i can make something out of it..

[Nadaka]

Before you jump on the A* bandwagon. You need to decide if you really want the shortest path, or if you want your monsters to react "realistically".

A* will always find the shortest path if your heuristic estimation is less than the actual shortest path.

A monster that acts realistically may have a limited knowledge of terrain, and will most likely have a limited knowledge of the location of the player.

A monster with only sight wont know where to go until it sees the player.

A monster with only hearing might not know where the player is until he gets within a certain radius.

A monster with only a sense of smell may not know where the player is until he crosses the players path and then follows it.

[SoulForged]

I want to make the standard pathfinding ALWAYS finding the player, because i want some monsters to be able to do so; then i plan to limit the standard monster by sight/hearing (depending on witch type of monster it is)

[SoulForged]

Thank you, the guide was really usefull, i completed the pathfinding IA and so far it seems to work fine..

[Soulwynd]

I had an article about rogue-like pathfinding that could be applied to other games and all. But well, the site went down. It's similar to dijkstra and a*. I call it aura path finding. I had vector path finding as well, but it was best used on non-tiled environments.

For rogue-likes, I'd go with an implementation of any aura casting methods. You can enhance it, however. to make things more interesting.

First of all, you want to make sure that if an enemy has visual contact, it ignores the original path finding. Second, you want to do the cast phase only once and use it for all creatures. Third, you can cast it once every 10 turns or so, so you don't have a huge path finding overhead.

Lemme give some practical examples.

Consider this map:

Code: [Select]

   1 2 3 4 5 6 7 8 9
 *------------------*
1|                  |
2|  ##########  ##  |
3|  ##          ##  | Each two spaces equals one tile.
4|  ##          ##  |
5|  ##          ##  |
6|  ##          ##  |
7|  ##              |
8|  ##  ##      ##  |
9|  ##  ##      ##  |
0|      ##      ##  |
1|  ##########  ##  |
2|                  |
 *------------------*

Now we place our hero (@@) and our monsters (M1, M2, M3) somewhere.

Code: [Select]

   1 2 3 4 5 6 7 8 9
 *------------------*
1|                  |
2|  ##########  ##  |
3|  ##          ##  | @@ = Player
4|  ##          ##  | M1 = Monster 1
5|  ##    @@    ##  | M2 = Monster 2
6|M1##          ##  | M3 = Monster 3
7|  ##              |
8|  ##  ##      ##  |
9|  ##  ##      ##  |
0|      ##      ##  |
1|  ##########  ##M3|
2|    M2            |
 *------------------*

First thing we do, is that we create a byte map with an aura cast from the player, starting with 0 and increasing with every direction. This map can be updated like every few rounds. Doesn't have to be precise... All it gotta do is get the monsters into line of sight so they can take a more direct method.

Code: [Select]

   1 2 3 4 5 6 7 8 9
 *------------------*
1|121110 9 8 7 6 7 8|
2|13########## 5## 9|
3|14## 4 3 2 3 4##10|
4|15## 3 2 1 2 3## 9|
5|14## 2 1 0 1 2## 8|
6|13## 3 2 1 2 3## 7|
7|12## 4 3 2 3 4 5 6|
8|11## 5## 3 4 5## 7|
9|10## 6## 4 5 6## 8|
0| 9 8 7## 5 6 7## 9|
1|10########## 8##10|
2|111213121110 91011|
 *------------------*

First thing you will notice is that you know the walking distance for each monster to the player. This is the most basic path finding you can do for your monsters in a rogue-like.

The problem is. It's not very realistic as the monsters would have some super ability to know where the player is. Plus take monster number 2. He can go either left or right. How would he decide. Here's were we can have more fun with this. You can have a byte map for noises the player make. His smell trail. Blood trails, etc.

Lets say the hero did something at square (3,7) like triggering a trap that created 10 points of noise.  Also lets say walls absorb 2 points of noise. So we cast a map for it that could decrease by 1 point every couple rounds, for example. Just so the monsters remember where the noises are coming from.

Code: [Select]

   1 2 3 4 5 6 7 8 9
 *------------------*
1|   1 2 1          |
2| 1###3#2#1## 1##  |
3| 2#3 6 5 4 3 2##  |
4| 3#4 7 6 5 4 3## 1|
5| 4#5 8 7 6 5 4#1 2|
6| 5#6 9 8 7 6 5#2 3|
7| 6#710 9 8 7 6 5 4|
8| 5## 9#6 7 6 5## 3|
9| 4## 8#5 6 5 4## 2|
0| 5 6 7#4 5 4 3## 1|
1| 4#3#4#1#2#1 2##  |
2| 3 2 3 2 1   1    |
 *------------------*

This can help monsters decide which path to take. A great thing is that it also defines a range for the noise. And if you want to be more realistic, you can use an exponential decay rate to simulate reality a bit better. But how can we apply this to the aura cast? That's simple. We just subtract these numbers from the aura byte map.

We can also say the hero is stinky from fighting and leaves a smell trail of 15 points that decay by one point per turn (which is a bit too fast, I wouldn't use that, maybe one point every 10 turns for that value) and that decay by two when cast from the player.

Code: [Select]

   1 2 3 4 5 6 7 8 9
 *------------------*
1|                  |
2|  ##########  ##  | Path the player might have taken.
3|  ##          ##  |
4|  ##          ##  |
5|  ##//--@@    ##  |
6|M1##||        ##  |
7|  ##||            |
8|  ##||##      ##  |
9|  ##||##      ##  |
0|//--//##      ##  |
1|||##########  ##M3|
2|||  M2            |
 *------------------*

   1 2 3 4 5 6 7 8 9
 *------------------*
1|                  |
2|  ########## 1##  | Notice how the path he took is much more smelly
3|  ## 911 7 5 3##  | than the rest of the room.
4|  ##121311 7 3##  |
5|  ##1415@@ 7 5##  |
6|  ##131311 9 7##  |
7| 1##1211 9 7 5 3 1|
8| 3##11## 7 5 3##  |
9| 5##10## 5 3 1##  |
0| 7 8 9## 3 1  ##  |
1| 6##########  ##  |
2| 5 3 1            |
 *------------------*

This could also be subtracted from the pathfinding map... Then all monsters gotta do is follow the nearest lower value. In this case, M2 would go left for example. Following both smell and sound the hero just made.

You can also avoid the aura cast at all, in that case, they would only follow by sound, smell and other senses. Meanwhile they could move around randomly or patrol until they actually saw/heard/smelled the player and so on. If there was some sort of alarm, you can then cast the huge aura to the player and let it work somewhat like L4D zombie rush, where every monster goes towards the player.


This can be used for a lot of things, btw. Like pointing out areas of interest for the monsters, or threat areas they should avoid, places they should gather, etc.

[kuro_suna]

I would use A* to path to random map points as a way to make the monster patrol around the map without getting stuck in U shaped terrain and do a line of sight test to detect the player and switch to attack mode if it does. The monster will store the last known location of the player and path to there as long as its in attack mode but go back to patrol mode if it goes too many turns without being able to see the player, this way the monster can pursue the player effectively but its still possible to evade it.

[SoulForged]

..

Thanks, this looks awesome.. i just have to think of how to complement the two methods efficiently..
The point is it looks a lot more "heavy" to calculate, and if i don't do it every turn the monster might just end up where i was some turns before instead of on top of me..

..

Yes, i think i'll let the normal moster act like this..

[Soulwynd]

if i don't do it every turn the monster might just end up where i was some turns before instead of on top of me..

You should try to get the monster in visual range. They can then use a simple move-towards-player formula instead of the pathfinding.

You can update this once every a few turns just fine. It's not as heavy as it seems either.

The monster pathfinding code can be defined with this simple metacode:

Code: [Select]

For each direction
  if not a wall
    Store aura[x][y] - smell[x][y] - sound[x][y] - areaOfInterest[x][y] value of the direction
  else if it's a wall, the value stored is maxed to avoid walking that way
Compare the stored values for each walkable direction
  if they are not the same
    walk towards the lowest value
  else
    walk randomly, or not at all

And you update the aura (if you want them to always go towards the player), the smell, sound, and any others you might want every few rounds.

So, for each monster, you're simply storing and working with 4 to 8 variables. The monster doesn't have to be aware of the entire pathfinding map, just the adjacent values. So it's pretty cheap, processor-wise. You only have one of each aura, smell, sound, etc for the map and every monster makes use of that. So while calculating pathfinding maps for huge places can be a lil bit more intensive, a single one can handle every monster in the map, making it quite effective.

[kuro_suna]

Just incase you didn't already know for line of sight http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm works well, also good for a fog of war system, just send lines from the player to points on a rectangle surrounding the player.

[Outcast Orange]

Here's an idea:

When it does the aura map, have it spread out from the player, around walls.
Think MS paint.
It adds one integer on every layer from the source, so the monster doesn't even have to worry about pathing.
You would have to weigh the calculation time against the A* calculation time,
but I think it would ultimately tie in better with the rest of the aura system.

[Soulwynd]

When it does the aura map, have it spread out from the player, around walls.

That's how it works.

I've made a demo for it. Lemme try to find it.

Here:
http://heathen.byethost13.com/temp/

Pick either (pick the .exe if you can't open 7zip files) and save as. Run, Have fun. It has a couple random map generators and shows the step ratio between casting an aura and actually following a path.

Virus scan, just in case:
http://www.virustotal.com/analisis/c3f5566e7c7cc380cb7bd6338bf040bdd1c7f25093764c7e6719d3bbe5a0f64b-1261697648

Forgot to mention:
@ = target (aura originates from this point, ie, player)
* = Monster (Or anything that wants to get to @)
# = wall
. = Aura
o = path

[Mr Tk]

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

A* is only as good as the heuristic you choose for it.