Any idea in implementing steering behaviour

General discussion about LÖVE, Lua, game development, puns, and unicorns.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Any idea in implementing steering behaviour

Post by Gunroar:Cannon() »

I wanted to mäke smooth pathfinding movement like in "the escapists". I used A* and made the object move to a node in the path(by small dt steps in update) until the position is met then move on to the next node in the path. But the check makes the object stop before getting there and then start again so it still looks blocky.
Then I thought of getting only the needed nodes(nodes that object can reach in a straight line) and using the same technique but now the stopping would be less noticeable...but I had trouble implementing it so I found https://gamedev.stackexchange.com/ques ... 1596#81596 and I still couldn't implement it(I'm like that sometimes :P :cry: ) but then I heard about steering behaviour and thought that's where I should go, looked at https://www.nonsequitoria.com/2521/ and https://natureofcode.com/book/chapter- ... us-agents/...but still had trouble implementing it (despite code examples but I don't know maybe right now I'm to impatient :cry: ).

So long story short(and that was pretty long) does anyone have any idea of how to do/an example of a lua implementation of steering behaviour(without love.physics, I just use bump.lua).
p.s. if anyone has any ideas on the corner-to-corner path thing(the first one with a link I failed at :cry: )that's welcome too.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
Carotino
Prole
Posts: 3
Joined: Thu Feb 18, 2021 9:00 pm

Re: Any idea in implementing steering behaviour

Post by Carotino »

Hi.
Right now I've found only this boids example in my disk, not done by me.

I actually implemented the algorithms from the original 80's paper years ago.

What I did then was having basically a point with a mass and a direction. You apply a force to direct it towards its next destination. When you start getting near it you select the next destination point. By applying forces your point will naturally change orientation smoothly, also depending on the mass of the point.
There could be many forces applying to the point: following others points in proximity, avoiding them, running away, looking for something.
I had a whole fish simulation with different roles (predators, prey, leaders, followers...). It was nice because after a while it started having a life of its own. Fishes started to school together (is it a sound verb? English is not my native tongue), then a predator made them fly in all directions, then a small fish found a leader and started following it, or they simply started to flock together, simultaneously following the others and trying to be no too close. All this sort of things.
Attachments
boids2.zip
(1.49 KiB) Downloaded 138 times
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Any idea in implementing steering behaviour

Post by Gunroar:Cannon() »

Carotino wrote: Thu Feb 18, 2021 9:57 pm ...
There could be many forces applying to the point: following others points in proximity, avoiding them, running away, looking for something.
I had a whole fish simulation with different roles (predators, prey, leaders, followers...). It was nice because after a while it started having a life of its own. Fishes started to school together (is it a sound verb? English is not my native tongue), then a predator made them fly in all directions, then a small fish found a leader and started following it, or they simply started to flock together, simultaneously following the others and trying to be no too close. All this sort of things.
Thnx a lot!
You used the school verb properly (I think :P).
Your examples was just what I needed :ultrahappy: ...but now I just want to ask about implementing a way for it to avoid obstacles which I once saw is possible in steering behaviour?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
togFox
Party member
Posts: 770
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: Any idea in implementing steering behaviour

Post by togFox »

I asked a similar question on avoidance here:

https://love2d.org/forums/viewtopic.php?f=4&t=90297

I love vectors and there is a very simple way to do path avoidance in my open world (no tiles).
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Any idea in implementing steering behaviour

Post by Gunroar:Cannon() »

togFox wrote: Mon Feb 22, 2021 10:43 pm I asked a similar question on avoidance here:

https://love2d.org/forums/viewtopic.php?f=4&t=90297

I love vectors and there is a very simple way to do path avoidance in my open world (no tiles).

Seems like it would work, though it doesn't use steering directly :ultrahappy:. Though I can think of a way to affect the vector given of by the steering, so...seems like it would work.
Heheh, though(me not being very good at math) doesn't really understand the weighted part:
Xii wrote: Sat Feb 13, 2021 3:40 pm If the number of entities isn't too high, what you can do is consider the distances and directions (vectors, essentially) towards each and every other entity.

Begin with a vector pointing straight to the goal, or something. Then, loop over all opponents. Subtract from the initial vector the vector towards each opponent, weighted by the inverse square [\b]of the distance to said opponent. Then have the entity move towards the final resulting vector. This creates avoidance behavior in real-time.


Could you/someone elaborate, pls.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Any idea in implementing steering behaviour

Post by Gunroar:Cannon() »

togFox wrote: Mon Feb 22, 2021 10:43 pm I asked a similar question on avoidance here:

https://love2d.org/forums/viewtopic.php?f=4&t=90297

I love vectors and there is a very simple way to do path avoidance in my open world (no tiles).

Seems like it would work, though it doesn't use steering directly :ultrahappy:. Though I can think of a way to affect the vector given of by the steering, so...seems like it would work.
Heheh, though(me not being very good at math) doesn't really understand the weighted part:
Xii wrote: Sat Feb 13, 2021 3:40 pm If the number of entities isn't too high, what you can do is consider the distances and directions (vectors, essentially) towards each and every other entity.

Begin with a vector pointing straight to the goal, or something. Then, loop over all opponents. Subtract from the initial vector the vector towards each opponent, weighted by the inverse square of the distance to said opponent. Then have the entity move towards the final resulting vector. This creates avoidance behavior in real-time.
Could you/someone elaborate, pls?

Edit:nooo!!! Pressed submit twice :P. Can't delete in this forum :cry:
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
Nikki
Citizen
Posts: 83
Joined: Wed Jan 25, 2017 5:42 pm

Re: Any idea in implementing steering behaviour

Post by Nikki »

https://natureofcode.com/book/chapter-6 ... us-agents/
this book is very nice and free



btw the weighing part is something like this in pseudocode
0.4 * pathfollowing + 0.6 * obstacle avoidance = the force you want to apply this frame


oh and obstacle avoidance is basically just calculating a force the opposite direction.
(but do have a look at the book its very nice, its by the same author as the coding train youtube channel (
https://thecodingtrain.com/CodingChalle ... paths.html
))
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Any idea in implementing steering behaviour

Post by Gunroar:Cannon() »

Nikki wrote: Tue Feb 23, 2021 5:23 pm https://natureofcode.com/book/chapter-6 ... us-agents/
this book is very nice and free

btw the weighing part is something like this in pseudocode
0.4 * pathfollowing + 0.6 * obstacle avoidance = the force you want to apply this frame

...

Thnx, I'll try to read that book (though I've seen it before and gone past it, but thnx for pointing it out again)...but...bear with me...I still don't get that weighted part. I mean, I check online before asking and I saw sigma signs, inverse square law, and a lot of stuff :shock: . So it just suprises me that it's that simple and that it has definite variables like 0.6.
I really want to just find out how to get the inverse square of a distance and then weigh it against intitial subtracted vector.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
Xii
Party member
Posts: 137
Joined: Thu Aug 13, 2020 9:09 pm
Contact:

Re: Any idea in implementing steering behaviour

Post by Xii »

Gunroar:Cannon() wrote: Tue Feb 23, 2021 11:03 pm I really want to just find out how to get the inverse square of a distance and then weigh it against intitial subtracted vector.
A point in 2-dimensional space is defined by two coordinates, x and y.
The distance between two points is:

Code: Select all

-- returns the distance between points x1,y1 and x2,y2
function distance(x1, y1, x2, y2)
	return math.sqrt(((x2-x1)^2)+((y2-y1)^2))
end
The square of a number n is n^2, or n*n (n raised to the 2nd power, or multiplied by itself)
The root of a squared number n, i.e. the square root of n, is math.sqrt(n)
The inverse of a number n is 1/n
Therefore, the inverse square root of a number n is 1/math.sqrt(n)
Putting it all together, the inverse square root of distance is therefore:

Code: Select all

function inv_sqrt_distance(x1, y1, x2, y2)
	return 1/math.sqrt(((x2-x1)^2)+((y2-y1)^2))
end
To weigh a vector by it is to multiply its components by it.
So if I have a vector {x,y}, the weighted vector is {x*d,y*d} where d is the inverse square distance.

Oh and to subtract one vector from another is to subtract the matching components:

Code: Select all

vector_one = {x1,y1}
vector_two = {x2,y2}
subtracted_vector = {vector_one[1]-vector_two[1], vector_one[2]-vector_two[2]}
What I like to do myself is use these...:

Code: Select all

-- returns the direction from point x1,y1 to x2,y2 (in radians)
function direction(x1, y1, x2, y2)
	return math.atan2(y2-y1, x2-x1)
end

-- returns the distance between points x1,y1 and x2,y2
function distance(x1, y1, x2, y2)
	return math.sqrt(((x2-x1)^2)+((y2-y1)^2))
end

-- returns the point located at x,y moved in direction by distance
function transposition(x, y, direction, distance)
	return distance*math.cos(direction)+x, distance*math.sin(direction)+y
end
First, the basic behavior; moving the actor towards the goal at some constant speed, making sure not to overshoot it:

Code: Select all

local dir = direction(actor_x, actor_y, goal_x, goal_y)
local dist = math.min(actor_speed, distance(actor_x, actor_y, goal_x, goal_y))
actor_x, actor_y = transposition(actor_x, actor_y, dir, dist)
Second, the avoidance behavior; moving the actor away from an obstacle at full speed:

Code: Select all

local dir = direction(obst_x, obst_y, actor_x, actor_y) -- note we reversed the coordinates.
-- before we got the direction from actor to goal, now we get direction from obstacle to actor
actor_x, actor_y = transposition(actor_x, actor_y, dir, actor_speed)
Third, weighted avoidance. We multiply the speed by the inverse square of the distance:

Code: Select all

local dir = direction(obst_x, obst_y, actor_x, actor_y)
local dist = 1/math.sqrt(distance(obst_x, obst_y, actor_x, actor_y)) * obst_radius
local speed = math.max(actor_speed, dist)
actor_x, actor_y = transposition(actor_x, actor_y, dir, speed)
obst_radius is a value >=1 that makes the avoidance behavior stronger the bigger it is. If the distance between actor and obstacle is less or equal to this radius, the actor will flee at full speed. The further away the actor is from the obstacle, the slower it will avoid it.

Finally, we combine everything:

Code: Select all

local goal_dir = direction(actor_x, actor_y, goal_x, goal_y)
local goal_dist = math.min(actor_speed, distance(actor_x, actor_y, goal_x, goal_y))

local avoid_dir = direction(obst_x, obst_y, actor_x, actor_y)
local avoid_dist = 1/math.sqrt(distance(obst_x, obst_y, actor_x, actor_y)) * obst_radius
local avoid_speed = math.max(actor_speed, avoid_dist)

local vector_x, vector_y = transposition(actor_x, actor_y, goal_dir, goal_dist) --towards goal
vector_x, vector_y = transposition(vector_x, vector_y, avoid_dir, avoid_speed) --away from obstacle

local dir = direction(actor_x, actor_y, vector_x, vector_y)
local dist = distance(actor_x, actor_y, vector_x, vector_y)
-- finally move the actor:
actor_x, actor_y = transposition(actor_x, actor_y, dir, math.min(dist, actor_speed))
...I think I got that right, anyway.

Note that this combined behavior will always move towards the goal, while also avoiding the obstacle. Which means that in theory if the obstacle is exactly between the actor and goal, the actor will stand still, not smart enough to go around it. :crazy:
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Any idea in implementing steering behaviour

Post by Gunroar:Cannon() »

Xii wrote: Wed Feb 24, 2021 6:59 pm ... Xii wrote a bunch of stuff, actually...
Haha, thnx for the 'from the very beginning' explanation ( it now ensures that there's no way for me to not understand anymore :ultraglee: :P ).
As for it not being able to move around obstacles...I really hope that my AI doesn't need to be that smart(*sweating smiley emoticon* :ultrahappy: )
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
Post Reply

Who is online

Users browsing this forum: No registered users and 47 guests