SOLVED Pathfinding without grids

Hello!
I've been searching a lot for pathfinding logics, also i took a look at some A* codes, but all of the ones i found uses grids for pathfinding, but in my game i don't use grids for movement, i want something more precise for my game instead of using grids (or end up using really small grids to get more precision on movement and stuff).
I use mouse for movement so i want to do some pathfinding for the player as well and not only monsters, so that's why using grids (at least big ones) would be horrible cuz it would lock the player movement a lot compared to what i have now wich is working nice and clean, the only thing is that my character slides along walls when colliding instead of finding a path around.

Am i making the wrong search for this type of logic i want?
Any ideas?
 

Umaro

Member
The built-in motion planning functions should avoid collisions. What are you using right now?
 
Well, one way to get around this is to use grids for the pathfinding, but do something more dynamic for the actual movement. So instead of heading directly towards the center of the next grid target, perhaps pick a random spot within the grid cell for the target. Or you can use something other than a grid, perhaps polygonal sections: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html. Or you can apply weights to your grid pathfinding to determine more organic paths between sections (if the trouble is that the paths generated on a grid move along one axis more than the other in a weird way).
 
The built-in motion planning functions should avoid collisions. What are you using right now?
Basically i'm using move_towards_point when i click because mp_potential_step does lots of weird movements for some reason.
I tried linear_step as well but move_towards_point works way nicer and also i'm using a custom collision mask wich have some code in it for the wall sliding.
 
Well, one way to get around this is to use grids for the pathfinding, but do something more dynamic for the actual movement. So instead of heading directly towards the center of the next grid target, perhaps pick a random spot within the grid cell for the target. Or you can use something other than a grid, perhaps polygonal sections: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html. Or you can apply weights to your grid pathfinding to determine more organic paths between sections (if the trouble is that the paths generated on a grid move along one axis more than the other in a weird way).

I'll take a look on how other types of "grid" can work so i'll have less "blocky" movements.
If i were to use really small grids it would be possible or it would be too much for the algorithm to handle?
 

Skull00

Member
For A* your nodes don't have to be aligned in a grid. I'm using it for pathfinding myself, but you will have to define the positions of each node yourself. This way you can use polygons of any shape to define the walls.

This is a pathfinding test project I made some time ago. It's not perfect but it works, also using A*. Sorry for the bad quality of the gif :D


Edit: It's actually the same thing from the link RefresherTowel has posted under the section "Polygonal maps"
 
For A* your nodes don't have to be aligned in a grid. I'm using it for pathfinding myself, but you will have to define the positions of each node yourself. This way you can use polygons of any shape to define the walls.

This is a pathfinding test project I made some time ago. It's not perfect but it works, also using A*. Sorry for the bad quality of the gif :D


Edit: It's actually the same thing from the link RefresherTowel has posted under the section "Polygonal maps"
I'm gonna take a look on this, but i managed to do it for now with mp_grid_path that activates only when there's a collision on a collision_line between the enemy and the player, otherwise it goes back to move_towards_point and it's doing pretty well for now :D!
But thanks a lot for the help and info all of you!
 
Top