Log In  

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.

P#41812 2017-06-20 15:20 ( Edited 2017-09-08 14:48)

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...

P#41813 2017-06-20 15:26 ( Edited 2017-06-20 19:26)

In the fourth PICO-8 fanzine, there's an article on A* pathfinding for PICO-8. Sounds like that would help solve your problem.

https://sectordub.itch.io/pico-8-fanzine-4

P#41816 2017-06-20 16:22 ( Edited 2017-06-20 20:22)

The author replied on Twitter to ensure the latest version of that A* pathfinding code is being used:

https://gist.github.com/richy486/b011a7d61a4e3612360f

P#41818 2017-06-20 16:35 ( Edited 2017-06-20 20:35)

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.

P#41819 2017-06-20 17:16 ( Edited 2017-06-20 21:16)

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.
P#41823 2017-06-20 20:04 ( Edited 2017-06-21 00:04)

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.

P#41824 2017-06-20 20:07 ( Edited 2017-06-21 00:07)

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.

P#41825 2017-06-20 20:38 ( Edited 2017-06-21 00:38)
1

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.

P#41829 2017-06-20 23:24 ( Edited 2017-06-21 03:24)

Here's an optimized and fully-general pathfinding routine in a single function:

https://github.com/morgan3d/misc/tree/master/p8pathfinder

P#44000 2017-09-08 04:06 ( Edited 2017-09-08 08:06)

You might also be interested in googling "Steering behaviors".

P#44004 2017-09-08 10:48 ( Edited 2017-09-08 14:48)

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2024-03-29 11:36:46 | 0.008s | Q:24