Need help with AI problem

Discussion in 'Intelligence & Machines' started by Xaque, Feb 11, 2004.

Thread Status:
Not open for further replies.
  1. Xaque Registered Member

    Messages:
    8
    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?
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. hlreed Registered Senior Member

    Messages:
    245
    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.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. malkiri Registered Senior Member

    Messages:
    198
    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.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. BigBlueHead Great Tealnoggin! Registered Senior Member

    Messages:
    1,996
    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).
     
  8. Xaque Registered Member

    Messages:
    8
    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.
     
  9. BigBlueHead Great Tealnoggin! Registered Senior Member

    Messages:
    1,996
    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.
     
  10. zanket Human Valued Senior Member

    Messages:
    3,777
    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.
     
  11. thefountainhed Fully Realized Valued Senior Member

    Messages:
    2,076
    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.
     
  12. Neurocomp2003 Registered Senior Member

    Messages:
    219
    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.
     
  13. malkiri Registered Senior Member

    Messages:
    198
    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.
     
  14. Xaque Registered Member

    Messages:
    8
    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.
     
  15. Neurocomp2003 Registered Senior Member

    Messages:
    219
    uh why a 486 machine?
     
  16. Stryder Keeper of "good" ideas. Valued Senior Member

    Messages:
    13,105
    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)
     
  17. artfldgr Registered Member

    Messages:
    5
    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
     
  18. Neurocomp2003 Registered Senior Member

    Messages:
    219
    i think the idea is that he wants to program it himself...to get familiar with the coding type.
     
Thread Status:
Not open for further replies.

Share This Page