Flocking/Herding

Game Discussion
Post new topic    
­BMR
Metal King Slime
Send private message
Flocking/Herding 
 PostWed Nov 21, 2012 6:50 am
Send private message Reply with quote
Ok, so I can wrap my head around the theory behind it, but I'm not sure if I'm implementing it correctly.

Currently, I've got this:

Code:

script, flock sheep, begin
   #Variable declarations
   #=====================
   variable(
      shc   #Sheep Count, the total number of sheep
      shr   #Sheep Reference, this is for the current sheep
      sht   #Sheep Target, this is for the target sheep
      
      curX  #The current X value
      curY  #The current Y value
      
      minX  #The minimum X value
      maxX  #The maximum X value
      minY  #The minimum Y value
      maxY  #The maximum Y value
      
      ctr1  #A counter used for working with the current sheep
      ctr2  #A counter used for the sheep that the current one will be compared to
      
      x1    #The starting X value
      x2    #The target Y value
      y1    #The starting Y value
      y2    #The target Y value
      
      wx    #The working X value
      wy    #The working Y value
      wt    #The working total sheep
      
      sr    #Search Radius, how far to search for a sheep
      
      dist  #The distance between the current sheep and the target sheep
   )
   #=====================
   
   
   
   
   
   
   #Generate variables
   #==================
   minX := 0
   minY := 0
   maxX := map width
   maxY := map height
   
   sr   := 16
   
   shc  := npc copy count(npc:sheep)
   #==================
   
   
   
   
   
   
   
   #This block will run through all of the sheep on the map
   #=======================================================
   for(ctr1, 0, shc) do(
      
      shr := npc reference(npc:sheep, ctr1) #Get the reference of the current sheep
      x1  := npc x(shr)                     #Get the X coordinate of the current sheep
      y1  := npc y(shr)                     #Get the Y coordinate of the current sheep

      wt  := 1                              #Reset the total sheep found
      wx  := x1                             #Reset the average X value of the sheep
      wy  := y1                             #Reset the average Y value of the sheep
      
      
      
      
      
      
      #This block will compare the current sheep to all the other sheep on the map
      #---------------------------------------------------------------------------
      for(ctr2, 0, shc) do(
         sht := npc reference(npc:sheep, ctr2) #Get the reference of the target sheep
         x2  := npc x(sht)                     #Get the X coordinate of the target sheep
         y2  := npc y(sht)                     #Get the Y coordinate of the target sheep
         
         trace value(x1, y1)
         trace value(x2, y2)
         
         dist := distance(x1, y1, x2, y2)  #Get the distance between the current sheep and the target sheep
         
         trace value(ctr2, dist)
         
         if(dist <= sr) then(  #If the distance is below the Search Radius, do the following
            wt += 1  #Increment the total number of sheep found
            wx += x2 #Add the target sheep's X coordinate for averaging later
            wy += y2 #Add the target sheep's Y coordinate for averaging later
            
            trace value(wx, wy)
         )
      )
      #---------------------------------------------------------------------------
      
      
      
      
      
      
      #Once the above is finished, the X and Y coordinates will be averaged to
      #find a new point for the sheep to move towards.      

      wx := wx / wt #Get the average X coordinate
      wy := wy / wt #Get the average Y coordinate
      
            
      #This will then make the sheep walk towards that point before resuming its Wander movement
      if(npc is walking(shr) == FALSE) then(
         walk npc to x(shr, wx)
         walk npc to y(shr, wy)
      )
   )
   #=======================================================
   
   
   set timer(timer:sheep, 1, 18, @flock sheep) #This resets the timer.
end



Currently, the code works. Sheep will generally just wander around the landscape minding their own business. When another sheep gets within range however, the average X and Y values of all the sheep in range will be calculated. The sheep will then head for that new value. This happens every 18 ticks.

My problem is, that although it does work, it does seem to be rather slow and clunky to operate. I was wondering if anyone had any suggestions as to how I might optimize the code (or even if I'm doing this correctly).

Thanks in advance, cheers!
Being from the third world, I reserve the right to speak in the third person.

Using Editor version wip 20170527 gfx_sdl+fb music_sdl
­TMC
Metal King Slime
Send private message
 
 PostWed Nov 21, 2012 12:49 pm
Send private message Reply with quote
Don't the walk npc to x/y commands cause the sheep to walk diagonally?

What distance are you using, Manhattan? And how many sheep are there?

Non-optimsations:
By far the slowest part of your script is the trace commands. Have you tried without them?

You could process just 1/18th of the sheep every tick.

Optimisations:
Are you aware of binning (space partitioning) methods? See eg. the Flocking article on Wikpedia. Simple idea, less simple to implement.

You can test first if a sheep is moving, and if so skip it.

BTW, off by one bug: replace shc with shc -- 1.

Off topic: What the, I can't use url blocks. Have they been disabled because of spammers?
­BMR
Metal King Slime
Send private message
 
 PostWed Nov 21, 2012 2:31 pm
Send private message Reply with quote
TMC wrote:
Don't the walk npc to x/y commands cause the sheep to walk diagonally?


Yes, it does. I'm also planning on implementing diagonal movement for the player. Failing that though, it'll be a simple switch to make the sheep go from diagonal back to orthogonal movement.


TMC wrote:
What distance are you using, Manhattan?


No, I'm using:

Code:

script, distance, x1, y1, x2, y2, begin
   #Variable declarations
   #=====================
   variable(
      x3 #Used in computations
      y3 #Used in computations
      
      rv #Return Value
   )
   #=====================
   
   x3    := (x2 -- x1)^2
   y3    := (y2 -- y1)^2
   
   rv := sqrt(x3 + y3)
   
   return(rv)
end


Should I be using Manhattan? I've read up about it, but am still unaware of the advantages/disadvantages of using that over this method. I'm not saying I favor any method over any other, I'm just genuinely unaware.


TMC wrote:
And how many sheep are there?


Right now, it's a random number, anywhere from 20 to 80 sheep. I'm thinking of lowering that though as I add other animals.


TMC wrote:
By far the slowest part of your script is the trace commands. Have you tried without them?


Well wow, removing them really sped up the code a lot. I had no idea they affected the speed to that degree.


TMC wrote:
You could process just 1/18th of the sheep every tick.


That sounds like a good idea, I'll look into figuring out how to implement it.


TMC wrote:
Are you aware of binning (space partitioning) methods? See eg. the Flocking article on Wikpedia. Simple idea, less simple to implement.


Nope, wasn't aware of it until you mentioned it. Reading up about it, it does indeed seem like a simple enough idea, but I'm not sure how I'd go about implementing it, though I'll certainly give it a go if the script bogs down too much.



TMC wrote:
You can test first if a sheep is moving, and if so skip it.


Hmm, good idea, I'll do that.



TMC wrote:
BTW, off by one bug: replace shc with shc -- 1.


That would be in the FOR loops?



EDIT: Hello my wee ickle sheepies!

Granted, very buggy-looking, and sheep get stuck on rocks and trees, and they pass through each other like ghosts, but it's getting there.
Being from the third world, I reserve the right to speak in the third person.

Using Editor version wip 20170527 gfx_sdl+fb music_sdl
­Minnek
Red Slime
Send private message
 
 PostWed Nov 21, 2012 3:34 pm
Send private message Reply with quote
The Manhattan distance heuristic is much faster, and yields acceptable results for A* and, perhaps, flocking. It's worth trying and seeing if the behavior remains within your idea of good. Since you're working with discrete locations (tiles), I don't see why it wouldn't be a good choice.

I second bin partitioning, too - you could probably use NPC extra data to store what bin they're in so that you can parse that later.
I... I still exist... somewhere.

Come join us on irc.esper.net in channel #slimesalad for help, chat, and general fun! We love company.
­TMC
Metal King Slime
Send private message
 
 PostThu Nov 22, 2012 12:13 pm
Send private message Reply with quote
Using Euclidean distance is fine, it's almost exactly the same speed is you use the following optimisation:

Code:
if((x1 -- x2)^2 + (y1 -- y2)^2 <= sr2) then(  #If the distance is below the Search Radius, do the following


Where sr2 is sr pre-squared. Note that assigning values to variables takes just as much time as calling a math operator.

I actually don't recommend using binning. 80^2/18 is quite small. Don't store the bins in the NPC extra data: if you need to iterate over all the sheep to find the ones in the neighbouring bins, then you gain nothing. Instead you need a way to directly retrieve all the items in a bin.

Anyway, about the sheep. It's not really how sheep act :P. Realistically they would be stationary at least 95% of the time, and walk much slower!
­Minnek
Red Slime
Send private message
 
 PostThu Nov 22, 2012 5:14 pm
Send private message Reply with quote
Shows what I know when dealing with plotscripting. Smile Would not have guessed the cost of assignment was the same as a math operator.

What if you used the NPC ID as the bin and then change NPC ID of each sheep to properly bin it as necessary? Then you could iterate over just that NPC ID's references on the map.

Alternatively, everybody's favorite fake arrays with globals using negative values to terminate each array? Then you can assign 100 globals to each array (should be plenty for the max sheep count?) You'd have to use a negative value different from -1 to identify the indices with removed sheep separately from the termination value if an npc reference can have the value 0, for when you're putting new sheep into each array. Clearly conjecture there, so who knows how it would do performance-wise compared to your current script.
I... I still exist... somewhere.

Come join us on irc.esper.net in channel #slimesalad for help, chat, and general fun! We love company.
­TMC
Metal King Slime
Send private message
 
 PostFri Nov 23, 2012 3:18 am
Send private message Reply with quote
(Anyone who cares about micro-optimisating scripts might find the benchmark.rpg collection of micro-benchmarks in the engine SVN repository helpful.)

Using NPC IDs for bins is pretty clever actually. I wouldn't have thought of that.

But if you used fake arrays of globals, then you need to make sure you update them efficiently (for example, when removing an item, swap the last item in the array into that position, rather than shuffling everything down). I think you would be better off using slice-based fake lists instead. Manipulating slices is slower than globals, though.
Display posts from previous: