Pathfinding is weird - any alternatives?

  • Hey,

    So I'm doing some stuff with pathfinding, and I'm noticing couple of very irritating things about it:

    1. The delay before movement

    2. Weird occasional "turning", that cannot be turned off.

    Do you know any alternative approaches that work better?

  • 1. The delay is unavoidable. Path finding can take a while.

    There are other methods but they depend on what you want to do.

    A* (a star) is what the pathfinding behavior uses and is the general purpose solution for simply finding a path as fast as possible. The "turning" can probably be avoided by doing the motion manually using the path points the behavior gives. If you roll your own with events then you could do things to make the delay shorter by exploiting the design of your levels.

    Like say your game consists of rooms then you could do a lower resolution search of just the path from room to room and then find a more detailed path for each room you move through. And on that note you might be able to do a progressive pathfind by doing a search on a coarse grid first and then perhaps using progressively finer grids.

    Also as a note, if you roll your own you could also use something besides a grid, like line segments for pathfinding to reduce the number of nodes to search through.

    Dijkstra's algorithm is another, which is slower but gives you the path from all grid cells to one or more points. It basically is a flood fill that starts at the destination then expands to the neighboring cells and stores the direction to move to get to the beginning cell. This is repeated until all the cells are visited. Then the moving sprites just need to use the direction of the cell they are currently on to know which way to move. Basically the path is only calculated once.

    I have an example here:

    For completely delay free pathfinding you could pre-calculate the path from every point to every other point.

    This guy did just that:

    The disadvantage is it's tedious to setup, but once it is the pathfinding will take no time at all. The cells are pretty big, but the idea is to just get the enemies in the general area and then use something simpler to move toward the player's exact position.

  • R0J0hound Hi, thanks for the extensive reply. I'm doing something similar to syndicate with a difference that you can select 4 agents like in rts. I just looked at quads example, but not sure how this could be implemented with my game. Any more suggestions will be highly appreciated! Meanwhile I'll look at Dijkstra example.

    EDIT@ I looked at second example, and it is really cool, but not sure if it what I currently need.

  • The delay often comes from

    1. too low rotation speed, set the Rotate speed of Pathfinding to something like 360 * 4

    2. too small cell size, try to make your cells as big as possible

  • The delay often comes from

    1. too low rotation speed, set the Rotate speed of Pathfinding to something like 360 * 4

    2. too small cell size, try to make your cells as big as possible

    Setting rotation to high speed worked!

    But, there is several of other issues:

    1. for some reason object cuts corners, which tells me that polygoal collisions are not taken under consideration, right?

    2. It is easy to break the behaviour, where when object is doing corner, you keep on clicking, then it will get stuck on it.

    3. There are still weird movement bounces, when object is next to the wall, and you change its direction, by clicking anywhere opposing to its movement.

    4. when object moves next to a isometric wall, it slightly bounces.

    capx http://drive.google.com/file/d/0B0jUjWN7LcQhbGE5STVXNUNoX2c/view?usp=sharing

  • You possibly could get away with doing something much simpler for a game like that. Most of the moves have a line of sight to the players and the obstacles look to be mainly just rectangles with no crevices.

    You could use line of sight and just move forward if the player has a clear view. If there is an obstacle in the way then just pick the furthest corner of the building that the player can see an move toward that, then they can continue to the goal as they round the corner. This should be able to work with many buildings, but the beauty of it is the player only addresses obstacles as they see them.

    It's simple and fast but can fail if you have alleyways instead of just buildings. I could be acceptable though, as I've played games where I had to help the player pick a better path. But now that I think of it you can mark the alleys in the editor so that the player can know to only go inside if the goal is in there. In a similar way you could mark long winding corridors I think, and just handle that in a unique way.

    EDIT:

    https://dl.dropboxusercontent.com/u/542 ... hfind.capx

  • R0J0hound Very interesting concept! The bullet can get slightly confused when there is more objects. What puzzles me thought, is that it overlaps with the gray boxes representing buildings, even thought both objects are solid.

    EDIT@ Would it be possible to connect your idea with pathfinding?! I think it is possible!

  • Woah, I was just passing by

    I fix an issue on my project

    Thanks

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • R0J0hound

    But how would you go about avoiding smaller assets and moving npc?

  • The player doesn't utilize the solid behavior, it's only used for the line of sight.

    It could be re-worked to utilize astar so the shortest distance is used every time, but it would have to be astar done from scratch, since it wouldn't be grid based.

    If smaller objects are passed through you could roll your own LOS with events with that in mind, or probably more appropriate implement some kind of collision response to push objects out of each other. Avoiding moving objects can be done by looking at where the objects will be a little in the future and if they are colliding adjust the current angle of motion so it won't.

  • The player doesn't utilize the solid behavior, it's only used for the line of sight.

    It could be re-worked to utilize astar so the shortest distance is used every time, but it would have to be astar done from scratch, since it wouldn't be grid based.

    If smaller objects are passed through you could roll your own LOS with events with that in mind, or probably more appropriate implement some kind of collision response to push objects out of each other. Avoiding moving objects can be done by looking at where the objects will be a little in the future and if they are colliding adjust the current angle of motion so it won't.

    Hmm, I have no idea how "looking in to the future" could be done. :/

    Maybe something simpler: how would you go about making characters not bump in to each other with just pathfinding? Also any suggestions how to keep formation when possible?

  • At any given moment a object has a position (x,y) and a velocity (vx,vy). Using a formula like rate*time=distance, you can guess what an object's position in the future will be: (x+vx*t, y+vy*t), where t is the number of seconds in the future. If the object's velocity does not change then the guess will be 100% correct.

    So checking in the future just means to move the objects to where they will be, check for overlaps, and then move them back.

    For formations each object has it's own goal, which is pretty straightforward.

    Collision response is what will allow units to not walk over each other or not walk over the walls.

    For units this is done by finding the distance between each pair of units and just move each away from each other if they are two close.

    For units against walls you find the distance to each side of the wall and use the closest side to push away from. This distance calculation is the distance from a line to a point, which is different from the distance from a point to a point.

    /examples26/simple_pathfind2.capx

    https://www.dropbox.com/s/lxzh1lizunezw ... .capx?dl=1

  • Tank on collision with Tank, Tank pick farthest from target x,y set speed to 0, system wait 1 second, Tank set speed to 100

    Bumper cars... sorta

  • At any given moment a object has a position (x,y) and a velocity (vx,vy). Using a formula like rate*time=distance, you can guess what an object's position in the future will be: (x+vx*t, y+vy*t), where t is the number of seconds in the future. If the object's velocity does not change then the guess will be 100% correct.

    So checking in the future just means to move the objects to where they will be, check for overlaps, and then move them back.

    For formations each object has it's own goal, which is pretty straightforward.

    Collision response is what will allow units to not walk over each other or not walk over the walls.

    For units this is done by finding the distance between each pair of units and just move each away from each other if they are two close.

    For units against walls you find the distance to each side of the wall and use the closest side to push away from. This distance calculation is the distance from a line to a point, which is different from the distance from a point to a point.

    https://dl.dropboxusercontent.com/u/542 ... find2.capx

    Thank you so much for all your help. I ultimately decided I will go with pathfinding. Since setting rotation to very high number got rid of that annoying delay, I wander if your technique of units not stepping in to each other would work with pathfinding too?

  • It probably can, since it just corrects the object's positions when they do overlap.

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)