Handling Enemies
Im writing a VERY simple tower defense game for a project, and im having some issues bringing everything together. i have a simple bot manager for the enemies and a manager for the towers. i also have a class handling the map. my problem is how do i pass information between the managers efficiently? for example, each tower has an array of enemies that it has in it's range. how does the tower get bot positions sent to it? i have an idea of how to do it but it is of O(n^2) which im not to thrilled about.
any ideas? does anybody have a link for me to read up on maybe? ive tried google, but i kept getting sites like "top 10 game enemies" lol.
thanks
-adam
Quote:i also have a class handling the map. my problem is how do i pass information between the managers efficiently?
Using references or pointers...
Quote:how does the tower get bot positions sent to it?
Why does a tower have bot positions sent to it? That doesn't sound like a typical function of a tower.
Please word your question more clearly, as I haven't a clue what you are actually trying to do.
If I had to GUESS what you are trying to do, I'd guess that you were trying to find all units that are within some range from a specific point. This is called a range search, and can be implemented in O(1) time using a regular grid if the distribution is uniform, or O(log n) time using a kd-tree for a general distribution.
Brute force should be quick enuf for a tower defense game + easier.
Ideally Though what you do is have a quadtree + see what leaves are within the towers shootrange. eg something like
quadtree->Return_leaves( const vec3 &pos, float radius, LeaveInfo *leaves );
Ideally Though what you do is have a quadtree + see what leaves are within the towers shootrange. eg something like
quadtree->Return_leaves( const vec3 &pos, float radius, LeaveInfo *leaves );
Quote:Original post by direwulfQuote:i also have a class handling the map. my problem is how do i pass information between the managers efficiently?
Using references or pointers...Quote:how does the tower get bot positions sent to it?
Why does a tower have bot positions sent to it? That doesn't sound like a typical function of a tower.
Please word your question more clearly, as I haven't a clue what you are actually trying to do.
If I had to GUESS what you are trying to do, I'd guess that you were trying to find all units that are within some range from a specific point. This is called a range search, and can be implemented in O(1) time using a regular grid if the distribution is uniform, or O(log n) time using a kd-tree for a general distribution.
sorry about the wording. i was in a rush before leaving work. the range search sounds like a good idea. how would i go about implementing it in O(1)? do you mean O(n)?
currently i have a botManager class, towerManager class, and a map class. the map class contains all of the tiles in the grid, and the models. the botManager handles all of the bots, and the towerManager handles all of the towers. i put a botManager and a towerManager inside of the map class so the map can call the updates. here is a quick example:
class Tower{ //...};class TowerManager{public: vector<Tower> towers; //...};class Bot{ //...};class BotManager{public: vector<Bot> bots; //...};class Map{public: BotManager botManager; TowerManager towerManager; //...};
should i just have the map class handle tower-bot searches?
[Edited by - adam17 on September 22, 2009 4:11:33 PM]
Quote:Original post by adam17
gow would i go about implementing it in O(1)? do you mean O(n)?
You just maintain a grid structure for each map cell, and each cell maintains a list of pointers to the units that are contained within the cell. Update these pointers when objects move.
When you want to find the list of units within a radius R from some specific point, you can just iterate over the grid cells that overlap this circle, and check each unit if it is within the radius.
This is technically O(n) worst case (the same as brute force), because you could just have 1 big cell that contained all your units, but if the distribution of units is uniform across a DxD grid, then each cell will contain roughly n/(D^2) units, and if you want to do a search with radius R (where R is measured in terms of the width of grid cells), then the exact complexity would be O( (R^2)/(D^2)*n ).
However, if the distribution is uniform, you can regard the number of units in each grid cell as a constant, and you can also regard the radius you want to search as a constant. This is why I wrote it as O(1).
If you pick a good grid size, the amortized time of this method can be much better than a kd-tree or octree, although those structures have better worst case performance.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement