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

What's the typical sort of ballpark value for "range"?

There's lots of little optimization faux pas in there, but nothing that should slow you down that much unless you're computing across ranges of like 10.

If you really need to compute across such large ranges, you're going to need some higher level optimizations, like not recomputing who you can hit if you don't need to.

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

If you need to search that many tiles, it's probably better to search enemies rather than tiles. Seriously, 80 tiles in a single direction means you're checking a grand total of almost 6400 tiles per unit.

Consider that if you have 300 entities, you're checking 300 things rather than 6400 things. For every unit in the game, that's 90,000 checks versus 1,920,000.

As far as higher-level optimizations beyond that, you need to subdivide your search space better. Check out quadtrees, for example.

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.

Depending on the entity's range, he only needs to search a limited number of chunks

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

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.

There is. Unfortunately, it's still going to be a quadtree or something similar. There's lots of ways to implement it, but one way you could do it is to create a bounding sphere as big as your range centered around the unit you're checking. Then zoom in on your quadtree structure until you've enclosed on the sphere as tightly as possible. Then just check all the units in that node.

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!

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);
            }
        }