123
-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|599|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Concept/Design -> Taking a Longer Path

Posted : Thursday, 21 March 2019, 05:22
spinal
anyone know how to do pathfinding where instead of the shortest path between a and b, you want to move an exact amount of moves without hitting any obstacles (including your own path)?

-=-=-
Check out my excellent homepage!
Posted : Thursday, 21 March 2019, 05:22
rychan
is it possible to use A* but set obstacles to have a crazy high value (thus negating them from the correct result)

-=-=-
Web / Game Dev, occasionally finishes off coding games also!

Refresh Games - Game Dev Blog
Posted : Thursday, 21 March 2019, 05:30
Jayenkai
I was thinking something like "pick a random point which is equidistant between A and B, at half the intended number, then pathfind to that point, then from there to the end point"..

It wouldn't be exact, though, so you'd probably need to do multiple iterations to find one that matches.

-=-=-
''Load, Next List!''
Posted : Thursday, 21 March 2019, 06:17
rychan
Ohhh, so if you wanted to do mobile object avoidance you could hittest the object against the squares and change their movement cost accordingly... Now I kinda wanna do A* pathfinding on the NES....somehow...errrr

-=-=-
Web / Game Dev, occasionally finishes off coding games also!

Refresh Games - Game Dev Blog
Posted : Thursday, 21 March 2019, 07:35
spinal
I was thinking something along these lines...



But only working out x number of moves while tracing each path and checking of obstacles. But I can't quick get my head around crating the path as an array of moves.
Also, the end point isn't so important either. So from A to wherever in exactly X moves safely.

-=-=-
Check out my excellent homepage!
Posted : Thursday, 21 March 2019, 07:39
Jayenkai
Eeek! Array that up!!!
Posted : Thursday, 21 March 2019, 08:26
Jayenkai
Made a brute-force thing..



It starts off searching for the exact distance, but slowly expands the amount if it can't find one, every 500 attempts.

-=-=-
''Load, Next List!''
Posted : Friday, 22 March 2019, 04:56
Pakz
Brute force can be very cpu intensitive with longer paths. A path more than 10 length is almost not doable I remember.

Maybe use looped a* or floodfill pather and randomly block some tiles every now and then until you come with the exact amount ? Maybe find the best path and step into a random direction a number of times until you get to the right amount?
Posted : Friday, 22 March 2019, 05:41
spinal
What I'm looking to do, is check for valid moved in my game and giving a game over if there are none. The rules of the game are simply move a specific amount of moves without crossing your own path or hitting an obstacle.
pathfinding sort of implies that there is a specific end point, which there isn't.
Oh and a maximum of 10 moves, which may or may not make things easier.

-=-=-
Check out my excellent homepage!
Posted : Friday, 22 March 2019, 07:25
Jayenkai
Only 10 maximum?
Yeah, you could definitely brute force that.

-=-=-
''Load, Next List!''
Posted : Saturday, 23 March 2019, 11:04
shroom_monk
I'd also vote for brute-forcing it. The requirement for an exact path length makes using any of the usual pathfinding algorithms unhelpful, but the lack of fixed destination writes them out entirely!

With 10 moves your search space should be small enough to be feasible, but even if it is expensive, if the game is based on a limited number of moves by the player then you only need to run it once per move, rather than once per frame.

Depth-first search will certainly be faster than breadth-first search for this, since you have a capped number of moves and you only care about whether a solution exists, not whether it's the 'best' solution.

-=-=-
A mushroom a day keeps the doctor away...

Keep It Simple, Shroom!