Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

106 Neutral

About Crashkurs

  • Rank
  1. Crashkurs

    Map datatype structure

    I implement the quadtrees again and it now works fine with 1000 units, thank you :)   Heres my solution: public List<LivingObject> getObjectsInRange(Vector3 _Position, float _Range) { Util.Circle circle = new Util.Circle(_Position, _Range); List<LivingObject> result = new List<LivingObject>(); getObjectsInRange(circle, this.quadTree.Root, result); return result; } private void getObjectsInRange(Util.Circle aggroCircle , QuadTree<LivingObject>.QuadNode currentNode, List<LivingObject> result) { if (Util.Intersection.CircleIsInRectangle(aggroCircle, currentNode.Bounds)) { //Circle fits in node, so search in subnodes Boolean circleFitsInSubnode = false; foreach(QuadTree<LivingObject>.QuadNode node in currentNode.Nodes) { if (node != null) { if (Util.Intersection.CircleIsInRectangle(aggroCircle, node.Bounds)) { circleFitsInSubnode = true; getObjectsInRange(aggroCircle, node, result); } } } //Aggrocircle fit into a subnode? then if (!circleFitsInSubnode) { addAllObjectsInRange(currentNode, aggroCircle, result); } } } private void addAllObjectsInRange(QuadTree<LivingObject>.QuadNode currentNode, Util.Circle circle, List<LivingObject> result) { foreach(LivingObject livingObject in currentNode.Objects) { if(Vector3.Distance(livingObject.Position, circle.Position) < circle.Radius) { result.Add(livingObject); } } foreach (QuadTree<LivingObject>.QuadNode node in currentNode.Nodes) { if (node != null) addAllObjectsInRange(node, circle, result); } }
  2. Crashkurs

    Map datatype structure

    Alright, i think im gonna try the quadtree again ;) i already have a function to check if a circle is in a rectangle, so im gonna use this for your solution. Thank you very much!
  3. Crashkurs

    Map datatype structure

    We already had Quadtrees and moved on to store the units inside the block it is belonging to and copied some attributes of quadtrees to chunks/blocks like giving objects which walked out of the bounds of the current block to the neighboor block. We moved on because we had problems with range checks in quadtrees when the entity in a quadtree is near its bounds and has to check the neighboors for objects in range.   The function i posted #1 already does it, blocks are 32px x 32px size and when the unit has 800 range, the algorithm will process 25 blocks into each direction, but thats a great amount of blocks checked, youre right .   Iterating over 300 entities for 300 entities( or less if they have a target) will result in about 90000 range checks for each update event, but maybe if theres a good way to remove entities from this range check list, its the way to go, im unsure right now.   Btw thanks for your help! I will try out some new stuff for range checks and then come back with questions for sure
  4. Crashkurs

    Map datatype structure

    Thanks for your reply, SeraphLance! The range depends on the entity, can be between 0 and about 800, so it may search up to 25 blocks to one neighboor direction.   Can you give me some keywords for those higher level optimizations? The entities can move every update event, thats why i check the range every event, because some new units may appear in range. As soon as a unit has a target, the searching for units in range will no longer execute, but our future plan is to create an aggro system and then the target may change to a target with higher threat, so i think we need to reorganisate our structure for better performance?! I would appreciate some hints what may be a better structure :)   Greetings Crashkurs
  5. Hey guys,   a friend and me are currently developing a 2d rpg game and having some trouble with efficiency for map structure. The structure yet looks like: 1 world, containing several regions. The regions itself contain an array of chunks(2x2) and every chunk contains an array of blocks(40x40), which have 32px x 32px size. Every block has a list of objects(entities, landscape, structures, e.g).   The function im working on is how to find entities in range around a point(can be a position of a unit) for aggro targeting, aoe spells e.g. Currently my solution is that every entity stores the block where it is in and then searches recursively for the blocks neighboors and checks whether these neighboors containing objects which are in range. Heres the sample code: -LivingObject is an entity for storing the position -These functions are stored in the block class(this. refers to a block) public List<Object.LivingObject> getLivingObjectsInRange(Vector3 _Position, float _Range) { List<Object.LivingObject> result = new List<Object.LivingObject>(); List<Block> visitedBlocks = new List<Block>(); getLivingObjectsInRange(_Position, _Range, result, visitedBlocks); return result; } public void getLivingObjectsInRange(Vector3 _Position, float _Range, List<Object.LivingObject> result, List<Block> visitedBlocks) { if (!visitedBlocks.Contains(this)) { foreach (Object.LivingObject var_LivingObject in this.objects) { float distance = Vector3.Distance(_Position, var_LivingObject.Position); if (distance <= _Range) result.Add(var_LivingObject); } visitedBlocks.Add(this); if (this.leftNeighbour != null && _Position.X - _Range < this.Position.X) this.leftNeighbour.getLivingObjectsInRange(_Position, _Range, result, visitedBlocks); if (this.rightNeighbour != null && _Position.X + _Range > this.Position.X + Block.BlockSize) this.rightNeighbour.getLivingObjectsInRange(_Position, _Range, result, visitedBlocks); if (this.bottomNeighbour != null && _Position.Y + _Range > this.Position.Y + Block.BlockSize) this.bottomNeighbour.getLivingObjectsInRange(_Position, _Range, result, visitedBlocks); if (this.topNeighbour != null && _Position.Y - _Range < this.Position.Y - Block.BlockSize) this.topNeighbour.getLivingObjectsInRange(_Position, _Range, result, visitedBlocks); } } The problem im facing is that this function drops the fps of the game from 60 to 2, when i create about 300 entities and every entity searches for other entities it can attack. This function gets called every update event as long as the entity has no target.   Do you have any suggestions on how we should structure our map data types or improve the functions to stay at 60fps? We are just in the beginning of the map development and entity storage so i would appreciate any hints how the storage and searching can be as efficient as possible   Greetings Crashkurs  
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!