Anyone have any links, examples or insight on how to make an object move towards a target while also going around obstacles (walls) when they hit them?
Say object A needs to get to object B (which is static). I can calculate the direction A needs to move, that's easy to get and make it move in that direction. But when it hits a wall on the way there, I'm not sure how to have it move around that wall.
I'm not necessarily interested in the shortest path, I just need A to get to B and have it be efficient enough for Pico8 to crunch it for several objects.
I'm aware that this will result in Gauntlet-style movement from the A objects around walls and such, which is fine.
Thinking out loud to myself...
So when the moving object A hits a wall, detect that and then add a small amount to the direction while keep trying to move...keep adding to direction until you are no longer hitting a wall.
Then on a interval, recalculate the directions towards the goal...
In the fourth PICO-8 fanzine, there's an article on A* pathfinding for PICO-8. Sounds like that would help solve your problem.
The author replied on Twitter to ensure the latest version of that A* pathfinding code is being used:
Yeah, I looked at that one a lot today while I was researching and exploring...didn't read the zine article though, that might help some. Thanks for the link...I see his tweet now too.
Thing is too I'm not looking for my objects to move along a grid, I want them to move smoothly...not sure how to bridge that gap even if I had the coordinates that create the 2D path.
One simple idea is to have "repulsion" and "attraction" vectors.
Say that your goal is your attraction vector -- so your object will move towards it. Your obstacles would have repulsion vectors (which are scaled by the distance, so that the farther they are the weaker they repulse).
Two problems with this approach for you to solve:
- You don't want to have ALL repulsors affecting all the time, or it will get expensive quick
- If the entity, the repulsor and the goal are collinear, the entity will not "dodge" the repulsor, so you might want to add some noise to the repulsor vector.
Another idea is to use object collision: Whenever your entity collides with an obstacle, calculate a vector between the center of mass of your entity and the center of mass of the obstacle, and add a perpendicular of that vector to the speed of your entity. This will cause "gautlet-like" movement where your entity hugs walls that get in its way.
Interesting idea with the repel/attract emitters. Might play with it a bit and see what happens.
Right now I'm only doing collision when walls are within X distance of an object so it's not checking a ton every tick...same thing could be used here.
Hey with A*, don't forget that you don't have to use it strictly for grid based movement. You can use it to make sure that it will find a valid path to the target, but you can adjust so that it's not using the optimum path.
Depending on how far away their target is, tracking 'breadcrumbs' can help too. The idea is like Hansel and Gretel -- store a limited list of previous locations (maybe once every 10 frames or so, going back a few dozen locations) and have the AIs attempt to follow them in order. And if they're within line of sight of the target, then just start following the target itself.
Here's an optimized and fully-general pathfinding routine in a single function:
You might also be interested in googling "Steering behaviors".
[Please log in to post a comment]
