Any idea in implementing steering behaviour

General discussion about LÖVE, Lua, game development, puns, and unicorns.
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Any idea in implementing steering behaviour

Post by pgimeno »

The inverse square of the distance is actually 1/d², it's NOT the square root. Since calculating the distance involves a square root, that square root cancels with the square. The result is:

Code: Select all

function inv_sqr_distance(x1, y1, x2, y2)
  return 1/((x2-x1)^2 + (y2-y1)^2)
end
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() »

pgimeno wrote: Thu Feb 25, 2021 2:43 am The inverse square of the distance is actually 1/d², it's NOT the square root. Since calculating the distance involves a square root, that square root cancels with the square. The result is:

Code: Select all

function inv_sqr_distance(x1, y1, x2, y2)
  return 1/((x2-x1)^2 + (y2-y1)^2)
end
Thanks for the correction!(Funny thing is that I had the function distance already so I was just gonna type 1/distance(...) :rofl: ).
So I should use distance without square rooting ?
And though the code uses angles to move(I tried with vectors here, but no luck). So to change it to vectors do I use cos and sine or...?

Edit: Tried it in anyway I could and it worked like magic!! Made some progression which come with new inquiries though...:
1)The code changes the angle to dx and dy, using math.cos and math.sine respectively,so I did this

Code: Select all

function boids:update(dt)
    local dx, dy=math.cos(self.angle), math.sine(self.angle)
    self.x = self.x+dx*self.vx*self.de*dt
    self.y = self.y+dy*self.vy*self.de*dt

    ...

    --defaults to one
    self.de = 1
    for _,i in ipairs(obstacles) do
        --i={x,y,w=10,h=10}
        local dist = unsquaredDistance(i,self)
        local sdist = math.sqrt(dist)
        local de = 1/dist
        --??check if close or else they all keep still??--
        if sdist<i.w then self.de=self.de*de end
    end
end
Is that fine for converting to vectors?

2)How do I deal with size and checking(I don't think I handled it well)?

3)What's the difference in 1/dist and 1/distrootsqred? When I root square it ,it even goes through gaps unlike the former, making it smoother, but that might be just because of my way of dealing with size.

4)What if the 'boid' gets stuck(which they do sometimes)?
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 »

What Xii has detailed (very well I have to say) is largely vector maths. It sounds scary but it's far easier to understand than calculus, algebra and even basic physics. I reckon if you spent one afternoon doing a medium dive into vectors and vector maths that script would make sense to you. :)
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: Thu Feb 25, 2021 10:17 am What Xii has detailed (very well I have to say) is largely vector maths. It sounds scary but it's far easier to understand than calculus, algebra and even basic physics. I reckon if you spent one afternoon doing a medium dive into vectors and vector maths that script would make sense to you. :)
No, you see :nyu: , the piece of code posted there makes sense to me, I even managed to adjust it to do what it needed to do,(thnx to that Xii's helpful comment) , and I just decided to post my implementation,

now I just have specific questions to clear up everything, especially how to deal with avoiding things based on size and what to do when the boid gets stuck due to trying to avoid something(I feel like getting the solution to the first one will solve the second one).
If the answers to this are in a link, you can provide one if you want.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Any idea in implementing steering behaviour

Post by pgimeno »

Gunroar:Cannon() wrote: Thu Feb 25, 2021 4:33 am 3)What's the difference in 1/dist and 1/distrootsqred?
At face value: none.

I can't tell about the algorithm, I just wanted to note that this question seems to confuse terms to a point where you're saying the same thing twice.

The formula of the distance between two points (x1, y1) and (x2, y2) is:

Code: Select all

  dist = math.sqrt((x2 - x1)^2 + (y2 - y1)^2)
The formula for the squared distance is:

Code: Select all

  dist_squared = dist^2
  -- expanding using the above formula we get:
  dist_squared = math.sqrt((x2 - x1)^2 + (y2 - y1)^2)^2
  -- and cancelling the sq.root with the squared:
  dist_squared = (x2 - x1)^2 + (y2 - y1)^2
Both alternatives for the squared distance give the same value (precision issues aside); the last formula just takes fewer calculations.

But you're asking about the "distrootsqred". The root of the distance (assuming "root" means "square root") is just that, the square root of the distance, and squaring it gives the distance, hence if distroot is the square root of the distance, distrootsqred is the distance. When you say "root" without a qualifier, it's often implied to be a square root; and when you say "x squared" it unequivocally means x². When taking your question at face value, you're asking what's the difference between the 1/distance and 1/math.sqrt(distance)^2. Obviously there's none besides a possible loss of precision due to the extra calculations.

I suspect you meant to ask about the difference between 1/dist and 1/dist_squared. I don't know the answer in relation to the algorithm you're using because I haven't tried to follow it.
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 »

pgimeno wrote: Thu Feb 25, 2021 2:43 am The inverse square of the distance is actually 1/d², it's NOT the square root. Since calculating the distance involves a square root, that square root cancels with the square. The result is:

Code: Select all

function inv_sqr_distance(x1, y1, x2, y2)
  return 1/((x2-x1)^2 + (y2-y1)^2)
end
I was looking at the sqrt in distance() and wondering if I made a mistake. Thanks for correcting!
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 »

If the size of the object is a factor and you want to 'flee' larger predators then after you determine your avoidance speed/velocity you can * by the size of the predator.

Small predators will reduce the delta velocity. Large predators will increase the delta velocity.
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() »

pgimeno wrote: Thu Feb 25, 2021 2:43 am The inverse square of the distance is actually 1/d², it's NOT the square root. Since calculating the distance involves a square root, that square root cancels with the square. The result is:

Code: Select all

function inv_sqr_distance(x1, y1, x2, y2)
  return 1/((x2-x1)^2 + (y2-y1)^2)
end
Xii wrote: Thu Feb 25, 2021 12:16 pm
...
I was looking at the sqrt in distance() and wondering if I made a mistake. Thanks for correcting!
That clears that up :awesome: !
togFox wrote: Thu Feb 25, 2021 1:14 pm If the size of the object is a factor and you want to 'flee' larger predators then after you determine your avoidance speed/velocity you can * by the size of the predator.

Small predators will reduce the delta velocity. Large predators will increase the delta velocity.
Hmmm, so, in essence, increasing the speed the bigger , nice, I'll try it.


Wow, you guys have really helped alot, the boids now can avoid obstacles. I decided to try and put them in a bump.lua world as a step closer to implementing them in my project. The boids still avoid the obstacles( :awesome: ) but there is one problem. This should be the last of my troubles if I can get this solved. A special case where the boid gets stuck between 2 tiles and refuses to move.
I've tried pushing it back when it hits a tile for to long and that seems to work when a single tile gets directly in its way but not for this type. I tried adjusting its angle by the opposite vector(made into an angle), but no luck. I've tried all I could think of?
Do you see any problems?:
Attachments
boidsAI.love
The code with residue of my attempts
(73.69 KiB) Downloaded 75 times
The scenariom the arrow is the boid and the white block at the top is the goal.
The scenariom the arrow is the boid and the white block at the top is the goal.
Screenshot_2021-02-26-10-41-48.png (67.22 KiB) Viewed 2843 times
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 »

Oh, you have a grid. My bad. Forget everything I said.

A* is the way to go. Instead of a binary "open/obstacle" value, generate a heatmap of your obstacles. A* will then "avoid" them on its way to the goal.
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: Fri Feb 26, 2021 8:55 pm Oh, you have a grid. My bad. Forget everything I said.

A* is the way to go. Instead of a binary "open/obstacle" value, generate a heatmap of your obstacles. A* will then "avoid" them on its way to the goal.
I don't really know how to do that :P :), but I think you're talking about including the obstacles in the grid so that A* will take it as a no-go area...
:ultrahappy: I wanted to mix A* and steering, https://gamedevelopment.tutsplus.com/t ... medev-8769, so that the moving from one node to another won't be stiff and would be smooth. I implemented the steering first without a grid then I added the grid to make it smarter and better at avoiding stuff and give it a higher collision when it has a goal, sometimes I would leave it in the game so its just roaming around without a path.
I managed to fix the stuck problem by fixing getTileP (getting a tile from pixel position, something was wrong with it), and by changing the angle to face the next node in the path every time it's supposed to move on.
So all your stuff was still really helpful :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 43 guests