Idea's?
BlitzMax Forums/BlitzMax Programming/Idea's?
| ||
| Was wondering how some of you would takle a small probably I have. Lets say I have two type's, one called bird, and one called food. there can be lots and lots of food on the ground, and you start with 1 bird. A bird moves, then checks to see if there is any food in front of it, lets say within 100 units. Now, I do this at the moment by doing a for eachin loop, checking the distance between the bird, and then all the food. this could loop 100 times. Now if I then have 20 birds, I am then looping for 20*n where n is the number of food. and each of them needs to check the food to see how far away from it they are. I think you can see that this will end up with lots of lag, if your sitting with 20+ birds all flying about, looking for food, and you have 100's of food to scan for distance. I know there is going to be a better way but its late and im not sure. So pls let me know any ideas you have. I had thought about creating a pre calculated list, of disctances, but thats no use because the bird moves so the table would be usless. |
| ||
| How about splitting the "map" into zones? Each zone has a list of food which is in that zone. Then just check which zone the bird is in and only check the food lists in the zone the bird is in and the neighbouring zones? I dunno, there are probably better ways, but that might spark off an idea. |
| ||
| Yeah, some kinda treestructure such as a quadtree perhaps? |
| ||
| I've heard that the zoning method mentioned above is the best. |
| ||
| I've got a similar problem with a space sim, with 300 ships and up to 1000 projectiles that need to be collided with them all. Fortunately they are pretty spread out, I'm going to try splitting the map into "zones" like Gabriel suggested. My problem is that being a space-sim, there is no maximum distance, and you can fly forever. I can't split it into infinity zones :p Maybe I could calculate the distance for everything from 0,0 and store it with the object. Then, I could run through the the objects and store them in a system of concentric circle zones, however many as are necessary for the furthest object. Easy, for sure, but not the most efficient zoning. Hard problem. |
| ||
| With a situation like yours, Will, I would definitely be looking at a quadtree ( if it's 2d ) or an octree ( if it's 3d ) because they create their own zones as they go. They eliminate huge areas very fast because they essentially split your entire world into four ( or eight ) and only subdivide those zones if they're visible. It may or may not be worth using a quadtree for Yavin's original problem, but I really think a quadtree or octree would work wonders for you. They're pretty simple to implement too. |
| ||
| Gab got examples of a quadtree. ? I am guessing the traversal code will need to be tweaked or slightly different to a basic tree to handle the extra node pointers? I may be wrong, an example would be awsome. I think I will try splitting the screen into 6 zones, 2 deep three across. If I get your idea corectly, I then have 6 TfoodTreeList's setup, and whenevr my code creates a new food, it checks the x,y and drops it into the correct tree. then when my Ai bird is scanning for food, it only scans for food in the same zone. This then means that if the bird is 1 pixel out from another zone, and the zone its in has a food at max distance, while the zone next to the bird has a food 5 pixels away I could have some problems. then again I could just add more zones. is it possible in Max to create an array of lists? |
| ||
| If I get your idea corectly, I then have 6 TfoodTreeList's setup, and whenevr my code creates a new food, it checks the x,y and drops it into the correct tree. Yes, exactly. This then means that if the bird is 1 pixel out from another zone, and the zone its in has a food at max distance, while the zone next to the bird has a food 5 pixels away I could have some problems.then again I could just add more zones. is it possible in Max to create an array of lists? Well my idea was to check neighbouring zones as well as the zone you're in. But you'd need more than six zones for that to be worth doing, yeah. Yeah, you can have an array of tLists. I don't have anything for quadtrees or octrees in Blitz any more, I'm afraid. Most of my old B3D code is gone. There's a nice tutorial on GameDev which I think I might have used when I was learning it. http://www.gamedev.net/reference/programming/features/quadtrees/ |
| ||
| Ah I c. thats clever. I might give that a shot, for the moment I am just going to go with a set amount of cells, and then test for food withing the root cell, and the 8 cells that suround the root cell. Once this is done it should cut down the iterations through the food lists from 1000's to only a few. I think I will also be adding some code so that it will only check the cells that are within its field of view and not the ones that its in. I will probably release the source cos Im only coding this as a refresher into max.. |
| ||
| What do you guys think I should do now... Ok so I have now implemented the lists, the screen is split up into 11*11 grid, each list holds any food found withing its grid(x,y) .. Now , when My bird or Droid needs to scan for food it needs to scan the root list, and then the 8 lists that suround it. I was thinking there are two ways to do this. 1. Scan each list individually, I cant really think of an easy way of sticking this in one loop, should would probably use 9 chunks of code. 2. Find some way if its possible, to do something like. templist : Tlist listaddlast templist,FoodArrayList[x,y] listaddlast templist,FoodArrayList[x+1,y+1] etc... and then just scan the temp list, then clearing the templist once the scan is done.. I am asking this here first because I dont have as much time as I used to to programme, so I waan be clear on what im going to do before i touch the code. |
   |