Need help with AI problem

Status
Not open for further replies.
X

Xaque

Registered Member
Here is what I am trying to do. I am writing a program in C++ that mimics the behaviour of a flock of birds by specifying 2 simple rules:
1. Do not get within 3 spaces of any other birds.
2. Do not get more than 7 spaces away from any birds.

The problem I am having is that I am somewhat new to C++ and I don't know an easy way for the birds to 'look' around and see what other birds are near them. Any suggestions?
 
You could probably do this better in a spread sheet. It already has the sweep.
In another sense, there is no way to do this in a computer. You must let each bird be a computer.
 
The most straightforward way to do this is something like:

For each bird Bi,
For each bird Bj,
Find distance from bird Bi to bird Bj and do the appropriate actions

May or may not be acceptable depending on how much processing you need to do in the inside. I'm sure there are ways to cut down on the unecessary or redundant work, but they may not be worth it.
 
What is the context for these birds? Are they in a continuous environment or something more like a cell grid?

For the most part, you're going to have to handle each bird individually as Malkiri says, which means that every new bird you add is going to have to check itself against all of the previous ones (so the complexity will increase very quickly as the number of birds increase).
 
The birds are in a cell grid. I tried something similar to what you are saying, but there are thousands of birds simulated at once, and it needs to be in real time, or close to it. What I really need is some sort of function that checks all the cells in a 10 cell radius around a single bird, then returns the ID numbers of the other birds, or something like that.
 
Try designing a hierarchical arrangement of birds, like a tree. Some root bird could stand as the centre of the flock, and designate the positions of n other birds at the proper distance around it.

Each of those n birds could control its own n birds at a certain distance.
Each of those n birds could control its own n birds at a certain distance.
And so on.

So, if you have a thousand birds, you could do the following:

Your initial (root) bird is in the middle.
It could control three birds.(3 + 1 = 4)
Each of these three birds controls three birds. (9 + 3 + 1 = 13)
Each of these three birds controls three birds. (27 + 9 + 3 + 1 = 40)
Each of these three birds controls three birds. (81 + 27 + 9 + 3 + 1 = 121)
Each of these three birds controls three birds. (243 + 81 + 27 + 9 + 3 + 1 = 364)
Each of these three birds controls three birds. (729 + 243 + 81 + 27 + 9 + 3 + 1 = 1093)

So, if you ensure that the original three birds are 6 * your maximum distance from the root bird, the second group of birds are 5 * the distance from their control bird, the third group of birds are 4 * the distance from their control bird, and so on, eventually you should have a system where most, if not all, of the birds are 1 "max" distance from their control bird.

I haven't thought this through too well, so my description's a little vague. But it would serve you well to handle this problem by subdividing.
 
Here are some ideas: Have an x, y, z array to represent the 3-d flock in space. A value of 0 for x, y, z means there’s no bird there. A value of 1 means there’s a bird there. The center of the whole x, y, z array is positioned in the sky somewhere; when that position changes it represents flock-as-a-whole movement. Maintain a list of positions for all the birds; if 5000 birds there are 5000 elements in this array. Traverse this list. Say you’re at bird #7. Create a function that, given an x, y, z position, returns a list of positions within a 10-cell spherical radius, minus positions that don’t exist (outside of the flock). Traverse that list for bird #7’s position, checking each position in the list against the x, y, z array to find all the adjacent birds. You can keep rotating through the list of birds. For each bird, it has to move to be as close as possible to be ((7 – 3) / 2) = 2 spaces on average from the adjacent birds. With each movement of a bird you recalculate where the center of the flock is in the sky.
 
Xaque said:
Here is what I am trying to do. I am writing a program in C++ that mimics the behaviour of a flock of birds by specifying 2 simple rules:
1. Do not get within 3 spaces of any other birds.
2. Do not get more than 7 spaces away from any birds.

The problem I am having is that I am somewhat new to C++ and I don't know an easy way for the birds to 'look' around and see what other birds are near them. Any suggestions?
Click to expand...
It all depends on how the program is meant to run. If you decide during runtime what the number of birds shall be, then your program must allocate the space.

It is a search algorithm solution.

You can create a matrix using arrays, or use double linked lists as your data structure.

If you use an array, use: 3(mxn) < mxn = number of birds < 7(mxn)
A link list is dynamically allocated and therefore, you hace no worries.

Once your data structure is created, traverse it using any search algorithm-- under the two constraints given. With a matrix, the programming is simple, as you can calculate the distances with ease using their positions. If you use a list, you have to create a class that keeps a number.

In anycase:
for ( birds <= # of birds)
---with current location a, previous location b
if a = bird, go to right a + 3,
b = a;
else
if ( distance ab < 7)
a = bird;
number of birds ++;
end if;
end if;
....something like that,

Or use a better search algorithm and input the constraints.
 
UM...actually there are alot of research done with "FLOCKING" which is what you are trying to attempt. You may be able to find code out there.

I suggest finding the website for this book and look at the flocking code
"COMPUTATIONAL BEAUTY OF NATURE" by Gary WFlake(sorry i don't have the website)
but also and pick up Game programming Gems I,II, or III there is flocking code in there too.

But I can also help. I know the theory behind(never programmed it myself)

2 questions
1) do you have memory constrictions
2) how big is the grid...

SOLUTION 1 (fastest for indicing,more memory)
If the grid itself is memory maintainable, have 2 variables one for the map
and one for the birds list. Then all you gotta do is access the indices array in the map for the cells nearest to your bird coordinates.

That is the (7+1+7)x(7+1+7) squares for you 7 cell rule and the (3+1+3)x(3+1+3) for your 3 cell rule. thus 15x15 + 7x7= <300 which is better than checking all your 10000+ birds

SOLUTION 2 (fast for indicing)
if grid memory cell by cell is to great....then divide into regions and subregions like first divide into 4 quadrants and another 4 quadrants
etc...till your memory suffices and then you just look at your bird down the
tree to the quadrants nearest to your bird. Bit harder to code but still does the job

SOLUTION 3 (slow for indicing but less memory)
sort of like the 1 answer above. But sort your birds in x and y orders
and place them in not hash but hash like table..(linked list within a linked list
list 1 sorts by x and within this list you have another list sorts by y
eg.
|----
|----
|----
|----

Less memory space expensive cuz your just storing the 10000+ birds
Then each time your birds move you gotta keep sorting, but the sortings is easier but a little more computationally expensive. Then to suffice your rules just go x+7 and x-7 and then y+7 y-7
So look at the x list and if in that range is empty its null
if range x is sufficed go down the lists for y and do the same.
 
thefountainhed:
If I understand your reply, you're suggesting a way to arrange a number of birds in an initial position that doesn't violate his constraints. I believe what he's looking for is a method for constantly updating the positions of the birds so that if they violate any of the constraints, they move in a direction that will allow them to satisfy them.

Some good suggestions by Neurocomp. In my opinion, the best option is #2. One way of implementing this is to use a quadtree. The cost won't increase as drastically as the original suggestion. The tradeoff is having to spend some time inserting the birds into the tree, updating their locations and sometimes which leaf they're in, and slightly more complex coding. In return however, you'll be able to query the tree for the 35 quadrants nearest to the bird's quadrant, and only check the distances for birds in those quadrants, each query taking logarithmic time. And that's only for the second constraint - if you are careful with the size of the leaf quadrants, you'll only need to check at most 8 quadrants for the first constraint.
 
Sorry for not replying for so long, I was on vacation.
I am writing this program for use on 486 machines, so there are fairly significant memory limitations. There can be a maximum of 2000 birds on the screen at any one time. I really don't want to put them in a tree or any thing as I want to implement other attributes such as color (birds of similar colors attract each other, or opposite colors repel) and other things. I probably should have said that in my original question.
I think these posts may have inspired a solution however, so thanks for your help. I've got some basic detection code for the birds that lets two birds keep an optimal distance between them while still "flying" randomly around. Now I just need to implement the search function that checks the other birds and it should be fine.
 
Looks a bit late for input, but I think what Hlreed should of said in a better term was about whether you wrote it to function as a Universal system where all birds locations are defined by the perimeters of the program, or where the program develops a Relative relationship, where you can generate a process that functions on it's own and then can become interactive with other spawned versions of itself.

Namely with each addition bird a iteration to the process occurs, so the same process can be used for each bird.

Looking at how you originally stated how a bird should work out it's relationship in conjunction with the others, I would guess that the method you would be looking at is the relative method.

Or as Hlreed put it "In another sense, there is no way to do this in a computer. You must let each bird be a computer."

(Just change computer to process)
 
in case you didnt know, what you are doing is reproducing work that went before. there is software that simulated flocking (that might be the name of it), and there are some interesting papers online if you take the time to search. the later generations of the software are used in movies today, not to mention other areas.. but you have seen the output even if you didnt know it.
its is a good example of emmergence. complex intelligent like behavior from simple rules.

look for BOIDs a program by cregg reynolds.. he is the one that solved the problems you are having and there are a lot of articles on it..

enjoy!!

artfldgr
 
Status
Not open for further replies.
Back
Top