Smart questions
Smart answers
Smart people
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Member Login




Remember Me
Forgot Password?
Join Us!

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips now!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

Join Tek-Tips
*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Donate Today!

Do you enjoy these
technical forums?
Donate Today! Click Here

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.
Jobs from Indeed

Link To This Forum!

Partner Button
Add Stickiness To Your Site By Linking To This Professionally Managed Technical Forum.
Just copy and paste the
code below into your site.

vb5prgrmr (Programmer) (OP)
29 Dec 08 0:36

(For those who have not followed the BOIDS link in thread1575-1517633: In the beginning..., BOIDS is the name for a specific flock, herd, or school AI simulation algorithm.)

A BOID is a singular autonomous unit among many. Meaning that a BOID is only aware of its immediate surroundings and has no memory of its past environment nor does it have any knowledge of its future environment beyond its range of vision, which makes this algorithm a unique opportunity to use in certain types of games to add flavor to the game. Games that I envision that this algorithm could be used in, are FPS (First Person Shooter) or FPF (First Person Fighter) games. With just a little modification this algorithm could be adapted to create a dumb hunting pack of creatures, like dumb zombies that roam the streets of the city and attack in packs or wolves or... well you get the idea. This algorithm would also be good for wandering monsters that travel in packs if you are into other fantasy type games.

So the behavior of a singular BOID is governed by its flock mates in that the nearby relatives determine its direction and speed of travel.

So how does it do this?

The Singular unit keeps itself separate from its flock mates (collision avoidance) by steering away from crowding its flock mates, but keeps itself within the group by a spatial averaging algorithm while keeping an average heading that is determined by its surrounding flock mates. Its speed is also determined by its flock mates barring any outside influences and the speed of the individual BOID should remain fairly constant unless the algorithm is modified for hunting packs or by being prey hunted by some predator, or some combination of both. Meaning two competing predators like the mongoose and the snake.

BUT...
Before we get to the plain English pseudo code, we need to determine or ask what information the BOID needs to be able to accomplish its task. So here is a list of questions that I came up with and if you can think of anything else, please add and please state your reasoning.

Where am I?
(A BOID really does not need to know where it is in its environment or on the map, but we do need to know this information so we can determine (or the BOID can determine) what is around it or in its field of vision. As for vision it is used loosely here to mean its area of perception where it can recognize other objects around it as in if you are building a game with strange creatures that rely upon say radar like bats do.)

What is my current direction of travel?
(As for a BOID, this is the only information it knows about where it is going. I say this in that the only information it knows is its direction because the BOID must figure out the rest from its flock mates but for a more complex AI this may be combined with other questions or information to increase realism.)

What are my vision parameters?
(Lets say the automated unit in question is a human soldier and from where this unit is looking, we can assume that on each side of its direct line of sight at about a 45 degree angle it will see anything in this 90 degree field of vision very well. However to simulate the peripheral vision which lets say is another 45 degrees on each side of the initial 90 degrees of forward vision, the unit will have a decreasing amount of visual capability to recognize things of significance. However, for a species that is normally considered prey, i.e. a BOID that does not have forward facing eyes like a fish, the range or angle of vision would be greater.)

What is my max vision range?
(For BOIDS and other autonomous units this must be known, as it will define the area of knowledge of their current environment but for both BOIDS and other units this value could be modified by local variables, i.e. does the water have more mud or silt in it here or is there smoke in the air? This also does not take into account the possibility of a unit having binoculars, a scope, or the view of a drone above or ahead of it or perhaps a satellite. Then again, the max vision range may not be able to be reached because of obstacles like trees, other units, buildings, and the terrain itself like a hill. Then when it comes to fog or smoke and the density of it, there is an area of semi clear vision and beyond that there is a decreasing amount of ability to see objects clearly.)



(This is, what I believe to be, the bare minimum amount of information we need for a BOID to operate effectively or at least be able to operate within the confines of what we want, but the BOIDS article claims to also use speed as a deterrent or method to also avoid collisions. However, from the many code examples that I have run and read, there are only a few that attempt to use speed effectively. So below are the questions about speed.)



What is my current speed?
(A BOID needs to know this especially since it may have increased speed to increase or decrease its separation from fellow flock mates or to pounce upon prey or to flee from a predator. Then again we would need this information if the unit was a vehicle of some sorts and its turning radius would be determined by its current speed.)

What is my max speed?
(If we have a game that has several types of units with varying capabilities, it would not be a good thing for a slow heavy unit to outpace a fast light unit. The same thing applies to flock mates in that if they are all fleeing from some predator, it would not be good for that singular BOID to flee faster than the others.)

What is my minimum speed?
(If your objects are anything like fish organisms then their minimum speed would be say one while if they are vehicles then minimum speed would or could be zero.)



(Now then, what is not discussed in the BIODS paper is limiting the BIODS capability of making turns. Meaning a tank, human, canine can turn in place while a car, fish, bird (while flying) need some forward motion (or reverse in case of a wheeled vehicle) to be able to turn.)



What is my ratio of turning capability based upon my current speed?
(While this does not raise the consequences of a speeding truck trying to make a sharp turn, it does, if used properly, keep a BOID or other object from doing something unnatural when making a turn.)



Okay, now that we have defined the minimum amount of information that we need for the BOID to operate, lets see if we can figure out some plain English pseudo code that will allow us to view a group of BOIDS operating. Then later we can add some more information for other capabilities like flee, pursue, or various ordered movements.



Current Position = Where I Am

What do I see? = some function that returns what I see around me based upon my vision range, my angle of vision, and modified by local variables like obstructions and modifications to my vision range via smoke, dust or silt in the water.

(From what I see I can now ask if my speed and direction match those of my flock mates and I can ask or determine if I am headed for a collision.)

Does my current direction and speed and the directions and speeds of those around me result in a collision or am I headed for a stationary obstacle?
    If yes then raise event for determining a new path and get out of this decision tree?

Is my spacing within the flock greater than my minimum personal distance or less than my visual range and is it an average distance between those that I observe?
    If not then I need to raise an event for determining a new path and exit this part of the decision process.

Does my current direction match the average of my fellow flock mates?
    If not then I need to raise an event for determining a new path and exit this part of the decision process.

Does my current speed match my fellow flock mates?
    If not then I need to raise an event for determining a new speed and exit this part of the decision process.

(If we made it here then we have nothing to adjust and need to allow the animation to continue.)
Then raise event for animation, collision detection, and potential collision detection to take over and exit this.



COLLISION AVOIDANCE

(Entering this Object means that a potential collision has been detected and we need to do something about it.)

Something from the left, then go right or change speed and let the object (flock mate) pass in front of me.
Then raise event for animation, collision detection, and potential collision detection to take over and exit this.

Something from the right then I need to turn left or change speed and let the object (flock mate) pass in front of me.
Then raise event for animation, collision detection, and potential collision detection to take over and exit this.

Stationary object then if it is to the left I need to turn right else turn left while trying to continue to avoid collisions by changing speeds if necessary.
Then raise event for animation, collision detection, and potential collision detection to take over and exit this.

Stationary object directly ahead, then if it has an angle to follow then I will turn in that direction else I will need to pick a direction, left or right based upon how much room I have and if they are the same then I will toss a coin and pick a direction while changing speeds to avoid collisions.
Then raise event for animation, collision detection, and potential collision detection to take over and exit this.



RESPACING WITHIN FLOCK

Find where I should be in the future and steer towards it while making sure that my new direction and speed do not result in a collision.
Then raise event for animation, collision detection, and potential collision detection to take over and exit this.




Now in the above scenario if this were to be coded for real, I hope you can see that I have placed collision avoidance at the top of my priority. (OK here comes the disclaimer) This by no means is the proper way for you to code your game. You may want to put a higher priority upon the actual flocking mechanism, or if you do modify the BOIDS algorithm for an actual hunting pack, you may want to allow collisions within the pack as if a couple of young wolves were at play while they wandered but they would avoid stationary objects. (Unless you wanted real realism and allow the wolf to rais a leg against some stationary object.)

If you have a different take upon the BOIDS information then please post your version.

You should also note (Okay, if you can't tell by my handle, I am mainly a VB programmer who prefers to prototype design in VB before going to C or any of its variants.) that the animation part of my algorithm is also an object. Which would raise an event for checking for potential collisions and collisions, which if true would raise an event for calling this AI to resolve those collisions or potential collisions more often for those units that need the CPU time than the guys that can forge straight ahead.


Please, if you have a different take, design, suggestions upon my design, want to discuss, whatever, please post.

BTW, if you have and or can understand VB6 code, there is an example at PSC (planet-source-code) called vbboids that you can search for and download. If you understand java, I believe that there is an example at sourceforge and while I was writing this in word and surfing some of the links that are not broken off the BOIDS page, I also found a C+ version of BOIDS source code but I can't remember where I found it now. However, I do remember that it was in the software reference section near the bottom of the BOIDS page.


 
vb5prgrmr (Programmer) (OP)
30 Dec 08 1:02

I believe the C+ version is at opensource...
Opieo (Programmer)
5 Jan 09 10:37
it would not be good for that singular BOID to flee faster than the others.

Unless of course, you would be that lucky BOID. Then by all means it is nice to be faster than your friends.
You do not need to be able to outrun a bear, only to be able to run faster than one of the friends you have with you.
=)

But in all seriousness I think it would be neat to have an ever so slight variance in the max speeds of a flock of BOIDS. In the case of prey, it seems like it would help preserve the survival of the fittest idea. At least until all that is left are all of the BOIDS that started off with the highest maximum.

~
"Your request is not unlike your lower intestine: stinky, and loaded with danger." — Ace Ventura.
 

vb5prgrmr (Programmer) (OP)
5 Jan 09 11:48
Made me smile

Yes, I believe if we were talking about anything but boids and ALS (Artificial Life Simulation) then you are correct. We would want to vary max speeds as the very young are not very coordinated and would be perhaps the slowest if not an injured while the young/young adult would not only be the fastest but have the endurance. Then of course the adult would have the higher cunning skill(evasion/pursuit), which would only be topped by the old who would be slightly slower and have less endurance.


 
gbaughma (IS/IT--Management)
5 Jan 09 15:50
What I learned from Boids is....

... you shouldn't light a cigar when a gas tanker has just overturned and spilled next to you.

;)

(alfred hitchcock reference there, btw)

 

Just my 2¢

"What the captain doesn't realize is that we've secretly replaced his Dilithium Crystals with new Folger's Crystals."

--Greg  http://parallel.tzo.com
 

vb5prgrmr (Programmer) (OP)
4 Feb 09 13:01

Okay, I went through all the links... (477) and found all 266 bad links, but I also found these links that are to code or links to code (only off the first page of external web site or programs for download.

http://www.dgp.toronto.edu/people/tu/papers/sig94.ps
http://www.virtualfishtank.com/
http://www.red3d.com/cwr/code/boids.lisp
http://www.smfr.org/computing/archaic/afterdark/
http://www.shef.ac.uk/uni/academic/N-Q/nuocpe/aquarium.html vb delphi pascal
http://www.cs.sjsu.edu/faculty/rucker/boppers.htm C/C+/C++ code
http://www.asahi-net.or.jp/~hq8y-ishm/
http://www.cs.ucl.ac.uk/staff/A.Steed/boids.html
http://www.planetsourcecode.com/vb/default.asp?lngWId=1 search vbboids
http://members.fortunecity.com/jngreenb/sim.html
http://ccl.sesp.northwestern.edu/cm/models/flocking/
http://www.geocities.com/pterandon/boids.html
http://www.povray.org/

BTW, I am slowly creating an Access db of all these links and will some day upload it but for know I have only processed the links from the first boids page.

Have Fun and Good Luck

 
vb5prgrmr (Programmer) (OP)
27 Feb 09 9:31

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members!

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close