Print

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

[Clownmite]

I vaguely remember that you could use your own callback function instead of using the tcod map class to do the pathfinding, if that helps. 

http://doryen.eptalys.net/data/libtcod/doc/1.5.1/html2/path_init.html?c=false&cpp=false&cs=false&py=true&lua=false

I think you just return a 0.0 the tile is blocked (by a wall or monster) and a 1.0 otherwise.

Thanks for the help - I had been looking at the custom blocked function thing. I guess I didn't articulate my question clearly: In order for the AI to take the most current information into account, it will have to loop through every single map tile AND every single object on the map, every single turn (and every AI entity would have to do this), so I'm trying to figure out if there's a better way.

[Levi]

I have no idea how Ultima RR is doing it, but the usual answer is to make the AI pretty dumb.   

Chances are each entity doesn't really need to know about every single tile to do what it needs to do.  Its generally just something like

1) Check my status
2) Check a target or two near me
3) Decide what to do with that, which is usually:
 - run away,
 - run towards
 - stab with the stabby sword

If you have a bunch of entities, then it'll probably look smart enough.

[Clownmite]

I have no idea how Ultima RR is doing it, but the usual answer is to make the AI pretty dumb.   

Chances are each entity doesn't really need to know about every single tile to do what it needs to do.  Its generally just something like

1) Check my status
2) Check a target or two near me
3) Decide what to do with that, which is usually:
 - run away,
 - run towards
 - stab with the stabby sword

If you have a bunch of entities, then it'll probably look smart enough.

That's actually exactly what my AI does right now (although the commander AI issues some pretty silly commands to the squad leaders, who either move where the commander tells them, or have their men charge). The issue is that when I have a squad of 10 vs another squad of 10, the pathfinding AI creates a traffic jam, where there will only be 1 guy from each side fighting, with the rest of the squad piled up behind them, each one trying to get at that "closest enemy" and not recognizing that there's another guy blocking their path. I can (and will, soon) change them to look for something other than the closest enemy, but that doesn't solve the core issue of them not realizing objects obstruct their paths.

[BishopX]

I have no idea how Ultima RR is doing it, but the usual answer is to make the AI pretty dumb.   

Chances are each entity doesn't really need to know about every single tile to do what it needs to do.  Its generally just something like

1) Check my status
2) Check a target or two near me
3) Decide what to do with that, which is usually:
 - run away,
 - run towards
 - stab with the stabby sword

If you have a bunch of entities, then it'll probably look smart enough.

That's actually exactly what my AI does right now (although the commander AI issues some pretty silly commands to the squad leaders, who either move where the commander tells them, or have their men charge). The issue is that when I have a squad of 10 vs another squad of 10, the pathfinding AI creates a traffic jam, where there will only be 1 guy from each side fighting, with the rest of the squad piled up behind them, each one trying to get at that "closest enemy" and not recognizing that there's another guy blocking their path. I can (and will, soon) change them to look for something other than the closest enemy, but that doesn't solve the core issue of them not realizing objects obstruct their paths.

You know, I'm not sure individual level path finding is that way to go in games like these. I mean historically anyone more tactically advanced than a tavern brawl fought with some level of coordination, even if it's only something as simple as "I'll stick with my mates so I'll have some to watch my back". To that end I think an AI descison tree like this:

-Check status
-Check for squadmates
-check for threats
-Make grade dependent descisions. For the grunts this would be:
     -If overwhelmed or cut of, run away
    -if ranged threat, respond/hold ranks/charge
    -if if opponents are close by attempt to engage while maintaining squad coherency.
For squad leaders you could add in slightly more advanced path finding, such are moving towards the enemy.

[Levi]

Maybe something like this:

Spoiler (click to show/hide)

Code: [Select]

#pseudocodeish
def path_func(xFrom,yFrom,xTo,yTo,map):
  if map.tiles[xTo][yTo] == ' ': #open space
    for unit in map.units:  #map.units will be a list of all your monsters/soldiers/ducks/whatevers
      if unit.x == xFrom and unit.y == yFrom:  #edit, skip if this is the current duck
        next
      if unit.x == xTo and unit.y == yTo:
        return 0.0  #tile is blocked if a unit is in the way
      elif (unit.x == xTo + 1 or unit.x == xTo - 1) and (unit.y == yTo + 1 or unit.y == yTo - 1):
        return 2.0  #double the cost to make ducks avoid clustering  (untested)
    return 1.0  #all good!
  elif map.tiles[xTo][yTo] == '#':  #wall
    return 0.0

path_new_using_function(width, height, path_func, map, 1.41)


In theory I think that would avoid the traffic jam issue.

Edit:  I should probably stop derailing the thread though.
Edit 2:  Fixed a logic error where unit would try to avoid walking next to himself.   

[Clownmite]

Maybe something like this:

**CODE**

In theory I think that would avoid the traffic jam issue.

Edit:  I should probably stop derailing the thread though.
Edit 2:  Fixed a logic error where unit would try to avoid walking next to himself.   

Thanks! I appreciate the help. And as long as nobody else is trying to carry on a discussion, and we're bumping this thread to the front page, I don't think derailing the thread is a bad thing.

I'm still having trouble understanding the custom function though - don't you need it to loop through EVERY tile on the map, along with every object? Here's my pathfinding function, and my move function:

Spoiler (click to show/hide)

Code: [Select]

def path_func(xFrom, yFrom, xTo, yTo, map):
if map[xFrom][yFrom].blocked or map[xTo][yTo].blocked:
return 0.0
else:
for object in objects:
if object.blocks and object.x == xFrom and object.y == yFrom:
return 0.0
if object.blocks and object.x == xTo and object.y == yTo:
return 0.0
return 1.0
return 1.0

Code: [Select]

def move_to(self, target_x, target_y):
global path_map, map
path_map = libtcod.path_new_using_function(MAP_WIDTH, MAP_HEIGHT, path_func, map, 1.41)
ai_move_path = libtcod.path_compute(path_map, self.x, self.y, target_x, target_y)
if ai_move_path and not libtcod.path_is_empty(path_map):
x,y = libtcod.path_walk(path_map,True)
if not is_blocked(x, y):
self.x = x
self.y = y


The trouble is obviously in my path_func - if I comment out the objects bit, it works fine (but the pathfinding doesn't take into account other objects: the very issue I want to solve); but if I keep the object code in, nobody moves. Any thoughts? Feel free to pm me if you don't want to clutter the thread.

[Levi]

Thanks! I appreciate the help. And as long as nobody else is trying to carry on a discussion, and we're bumping this thread to the front page, I don't think derailing the thread is a bad thing.

I'm still having trouble understanding the custom function though - don't you need it to loop through EVERY tile on the map, along with every object? Here's my pathfinding function, and my move function:

Spoiler (click to show/hide)

Code: [Select]

def path_func(xFrom, yFrom, xTo, yTo, map):
if map[xFrom][yFrom].blocked or map[xTo][yTo].blocked:
return 0.0
else:
for object in objects:
if object.blocks and object.x == xFrom and object.y == yFrom:
return 0.0
if object.blocks and object.x == xTo and object.y == yTo:
return 0.0
return 1.0
return 1.0

Code: [Select]

def move_to(self, target_x, target_y):
global path_map, map
path_map = libtcod.path_new_using_function(MAP_WIDTH, MAP_HEIGHT, path_func, map, 1.41)
ai_move_path = libtcod.path_compute(path_map, self.x, self.y, target_x, target_y)
if ai_move_path and not libtcod.path_is_empty(path_map):
x,y = libtcod.path_walk(path_map,True)
if not is_blocked(x, y):
self.x = x
self.y = y


The trouble is obviously in my path_func - if I comment out the objects bit, it works fine (but the pathfinding doesn't take into account other objects: the very issue I want to solve); but if I keep the object code in, nobody moves. Any thoughts? Feel free to pm me if you don't want to clutter the thread.

Nope.  The a* algorithm is the one that calls the function whenever its appropriate.  The custom path function ONLY tells the A* algorithm if the current cell is accessible or not.

Your code is almost right I think.  I'd take out all the checking of the xFrom and yFrom.  Only look at xTo and yTo when doing the comparisons.  The problem is that xFrom and yFrom are probably always going to match against the unit who is trying to move.  He is essentially blocking himself.  So your code would be more like:

Spoiler (click to show/hide)

Code: [Select]

def path_func(xFrom, yFrom, xTo, yTo, map):
if map[xTo][yTo].blocked:
return 0.0
else:
for object in objects:
if object.blocks and object.x == xTo and object.y == yTo:
return 0.0
return 1.0
return 1.0


I think that would probably work.

Edit:  I'm actually working on some similar code that is having a few technical problems.  If I get it worked out I might have a better idea of how to make things more efficient too.

[Clownmite]

Nope.  The a* algorithm is the one that calls the function whenever its appropriate.  The custom path function ONLY tells the A* algorithm if the current cell is accessible or not.

Your code is almost right I think.  I'd take out all the checking of the xFrom and yFrom.  Only look at xTo and yTo when doing the comparisons.  The problem is that xFrom and yFrom are probably always going to match against the unit who is trying to move.  He is essentially blocking himself.  So your code would be more like:

Spoiler (click to show/hide)

Code: [Select]

def path_func(xFrom, yFrom, xTo, yTo, map):
if map[xTo][yTo].blocked:
return 0.0
else:
for object in objects:
if object.blocks and object.x == xTo and object.y == yTo:
return 0.0
return 1.0
return 1.0


I think that would probably work.

No, if I try that the game freezes up (and if I do this:

Spoiler (click to show/hide)

Code: [Select]

def path_func(xFrom, yFrom, xTo, yTo, map):
if map[xTo][yTo].blocked:
return 0.0
else:
for object in objects:
if object.blocks and object.x == xTo and object.y == yTo:
return 0.0
else:
return 1.0
return 1.0

It runs, but again, they don't take each other into account when pathfinding.

What I don't understand is the purpose of the xFrom, and yFrom in that definition. How does the path function know the xFrom and yFrom, since they're never specified? Why does xTo and yTo even matter: Shouldn't this definition be just building a path map by looking at all map tiles and checking which ones are blocked?

[Levi]

It freezes?   I don't have an explanation for that.   


The change you made doesn't take each other into account when pathfinding because it just looks at the first unit and then returns 1.0.  It should look at all of them, and then return 1.0 if none of them matched.

[Leatra]

Erm... No offense but you guys could discuss this with MSN or something too you know

[Levi]

No, you are right.  I'll keep it in pms or in the programming help thread.  Sorry about that!

[klingon13524]

Bump, because this seems like exactly the game of my dreams.

[Enzo]

I don't know if bumps are necessary on a day-old topic :/

[KaelGotDwarves]

Posting to encourage and to follow the project.

[Rex_Nex]

Same as above. Hoping to see URR become something grand