Boids - group AI implemented in ThinBASIC

[Petr Schreiber]

Hi,

during Game Access 2010 there was one nice technique mentioned "by the way" as approach used for modelling chicken flock animation - the boids.

I googled a bit on the topic, it seems it is one of the most elemental algorithms for group AI, but I like it very much so I present it here in version, where "boids" (individual members of flock) are visualised as simplified fishes in the sea.

The code is organised again around entities and concept of actors and animators I mentioned a while ago. It is very close to OOP and for now it seems very natural way to implement ideas in TB (at least for me :p).

The actors are the boids, that means fish in this case, the animators handle the flock behavior. There are two flocks in the demo, one are prey and second the predators.

The code is strongly based on great pseudocode from here:
http://www.vergenet.net/~conrad/boids/pseudocode.html (http://www.vergenet.net/%7Econrad/boids/pseudocode.html)
where the 3 main rules - position, collision avoidance and speed matching are discussed in detail and very clear fashion.

You will need thinBASIC 1.8.6.0 (http://www.thinbasic.com/community/showthread.php?10672-thinBasic-Beta-1.8.6.0) + latest TBGL (http://www.thinbasic.com/community/showthread.php?10909-The-latest-TBGL-version) to run it (or anything newer).

It is not meant to be visually very impressive, I could create model for the fishes and animate it, but I wanted the code to stay as "pure" for general boids as it could be, so others can use it in their projects. That is why fishes are represented just with elipsoids.
As said before, code is strongly OOP, so you can "instantiate" as many boids and their flocks as you need in your projects.

The main application can be launched from Boids_DemoApp.tBasic, the actor_boid.tBasic and animator_boid.tBasic are just "units" used by the main code.


I hope you will like it,
Petr

UPDATE: Added new download of BoidsEnhanced.zip where you can play more with the script:


Arrow keys to move view
F5, F6 to change area used for prey
F7, F8 to change area used for hunters
F9 default camera
F12 hunter camera

[kryton9]

I'm getting an error Petr.

Line 64, I corrected by making it like this:
TBGL_EntitySetScale(%sScene, eBoid, Rndf(1, 1.1),1,1)

Line 83:
TBGL_EntitySetScale(%sScene, eBoid, 2,1,1)

Thanks for the demo. I had to make it bigger resolution so I could see it. The current screensize was just too small.
hWnd = TBGL_CreateWindowEx("Demo of Boids for ThinBASIC - press ESC to quit", 1024, 768, 32, %TBGL_WS_FULLSCREEN)
Will be good study material, so thanks again.

[Charles Pegge]

Thanks Petr,

Glad I am not a fish!

Very interesting AI and a powerful basis for more complex behaviour. - I will retain this for reference.

Charles

[Petr Schreiber]

Kent,

the problem you had was because of old TBGL, that is why I mentioned necessity to update it in the original post. New release allows specifying single factor for scale, as it is the most used scenario and saves some coding. The equivalent of:


TBGL_EntitySetScale(%sScene, eBoid, Rndf(1, 1.1))
is in old TBGL something like this:


DIM factor AS Number = Rndf(1, 1.1)
TBGL_EntitySetScale(%sScene, eBoid, factor, factor, factor)
Thanks for trying and for the comments, you are right it is not visible very much, I made it even harder by using fog :) But I liked the feeling when the fishes are almost invisible, then change direction and thanks to specular material their bodies shine in the light from the dark.

Charles - thanks! I am sure it could get serious performance boost using Oxygen, as it uses lot of loops. With bigger number of fishes it becomes a bit slow here.

The use of this technique is not limited to fishes, but also to birds, sheeps (and other animals organised in "hordes") + for example for part of movement AI in FPS or strategy games, where group of characters travel through environment.


Petr

[Petr Schreiber]

As this demo is not very intensive on fragment operations, it could be also possible to directly switch to desktop resolution immediately without any hesitation:


Dim width, height, bitDepth As Long
TBGL_GetDesktopInfo(width, height, bitDepth)
hWnd = TBGL_CreateWindowEx("Demo of Boids for ThinBASIC - press ESC to quit", width, height, bitDepth, %TBGL_WS_FULLSCREEN)
TBGL_ShowWindow



Petr

[kryton9]

I downloaded the latest tbgl before I ran the demo Petr. I must not have installed it correctly, will check again. Thanks.

[Petr Schreiber]

Hi Kent,

after I read about your problems, I deleted TBGL from Lib directory, downloaded the one marked as latest, "installed" it and the script works fine. Maybe you really just extracted it to other folder. Please let me know.

Another possibility is that in folder you extracted script to there is old thinBASIC_TBGL.DLL placed by some weird accident.

I attach what you should see when looking at thinBASIC_TBGL.DLL in your Lib directory (of course it is from Czech Windows, so some things will be a bit different ;))


Petr

[kryton9]

Thanks Petr. I must have clicked on one of the windows 7 prompts wrongly and not replace what was there, that is all I can think of.

It is working fine now. Again really cool to watch, good job!

[Lionheart008]

hi petr, I have tried your swimming animals and boids_demoApp works fine. I have resized the camera to 10,10,10 to see more of the swarm ;) but perhaps here's a mistake.. "actor_" + "animator_boid.tbasic" files there may be a problem with
"tvector3f" . I have installed new tbgl version and copied new tbgl dll into lib folder. interesting work, thanks for sharing that! :) frank

[Petr Schreiber]

Kent,

I am happy it finally works for you, perfect :)

Frank,

the actor_* and animator_* files are just include files, which are not supposed to be launched separately. The Boids_DemoApp.tBasic is the main application which uses them.

The reason you get the run time error when trying to launch them separately is because they use type defined in TBGL. The main application uses "TBGL" and then includes these files, that is why it works in the main app and not alone. But this is by design.

Thanks for trying!


Petr

[Lionheart008]

hi petr,

the actor_* and animator_* files are just include files, which are not supposed to be launched separately. The Boids_DemoApp.tBasic is the main application which uses them. .. it's for me still unusual to use tbasic files as include files, so I was confused for a moment, but I understand your project tree (*grinning*). I will try to use it for one of my next tbgl example.

here is another question:

a) it's possible to texture irregular (not plane) formed object (tbgl_vertex, tbgl_ngon), I mean no cube or triangles, with mapped texture: perhaps for another example a nurbs surface ?
b) how would you texture such a fish? ( in general)
c) what about speed behaviour if you are using three, four different texture for rendering ? do you have any experiences with rendering speed in such cases? that's a problem I am running in my mind at the moment, because I've got quite different framerates with textured background in one of my powerbasic openGL examples.. so I can imagine that's same problem for tbgl behaviour (or you have already missed this lack! ;) )

best regards, thanks, frank

[Petr Schreiber]

Hi Frank,

yes, using tBasic for includes is not very usual. I will talk to Eros about possibility to create new extension, such as .tBasicU (unit) for thinBASIC, as .inc used till now is quite common in other BASICs as well, so it sometimes opens in wrong IDE when you click it. That is why I stopped using this extension of my TB projects.

a) I am not sure I understand the question . Any shape you design using todays graphics hardware (maybe with exception of points and lines) is represented as triangular mesh. So texturing single triangle can be done the same way as multiple triangles. I do not like the glu implementation of NURBS, that is why I do not post examples on it. It could be nice to create own implementation of it, but that would mean some time spending on it and currently I do not have any use for it.

b) :) I would probably texture fish in the 3D editor of my choice, then export it to OBJ, convert to M15 and use it in script.

c) Texturing is operation where few common rules apply, and other depend simply on hardware horsepower. It is ok to have multiple textures, but what affects the performance most is generally is:


how often do you change the active texture. The less changes, the better performance.
dimensions of the texture. Even on modern hardware, the power of two textures usually give better performance than images of "any size". Large resolution textures (8192x8192) are slightly slower to process than smaller ones.
which filtering mode is activated. Anisotropic filter is the nicest one, but also the most expensive performance wise. The mip mapping (aka trilinear filtering) can be faster, but it occupies more memory, because from each texture there are clones done - if you have 512x512 texture, it is internally stored as 512x512+256x256x128x128+... set of textures, which are then looked up by the rasterizer... and so on


Petr

[zak]

a fantastic project, ( unbelievable ), thanks Petr, i guess in the code "which i can't follow now" no single fish will collide with other fish, so this is usefull in ai machines in which it is prohibited for it to collide with environment objects.
in my viewing i changed fog density to "1" so i can recognise the fishes more.
zak

[Petr Schreiber]

Thanks Zak, I somehow missed your reply

I posted slightly modded BoidsEnhanced.zip demo to the first post of this thread, where visibility is much better and you have more controls (rotating view, changing camera, limiting space for fishes...).


Petr

[ErosOlmi]

I promoted this thread as Article in Article area.
Too great example to miss it.