6 Replies - 1527 Views - Last Post: 22 February 2012 - 07:49 PM Rate Topic: -----

#1 hawksprite  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 7
  • View blog
  • Posts: 137
  • Joined: 11-September 09

Astar Path finding in large tile based worlds.

Posted 22 February 2012 - 04:11 PM

So here's a general game developing question for you. Recently I've been working on Dark Castle a top down zombie horror survival game and I've run into a problem. I developed an method for path finding in the game grid with aStar, but after implementing a map editor and vastly expanding the underlying "grid" it's become to much of a performance problem.

What's the standard for handling these situations? My guess would be splitting the grid up into regions but i'm not sure how to go about this because it's a List<Node> gridPiece type of deal, for me to loop through them all and check for things to mark them off each cycle would be to resource intensive.

If you need example code and snippets i'll be glad to post more information but because it's XNA based I decided to keep it mostly "theory" so i could reach the broader audience of the game development board; hope this isn't a problem.

Is This A Good Question/Topic? 0
  • +

Replies To: Astar Path finding in large tile based worlds.

#2 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 1
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Astar Path finding in large tile based worlds.

Posted 22 February 2012 - 04:16 PM

Yes, this is because your algorithm is scanning the entire space. Have you reviewed Binary Space Partitioning?
Was This Post Helpful? 0
  • +
  • -

#3 hawksprite  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 7
  • View blog
  • Posts: 137
  • Joined: 11-September 09

Re: Astar Path finding in large tile based worlds.

Posted 22 February 2012 - 04:56 PM

I haven't looked into Binary Space Partitioning, I'm self taught so I'm not sure what standards or methods I should be considering thanks for the help.

Through some testing I found some very specific bottle necking points. One of which gets the current grid tile "id" which scans through the whole grid.

I tested this problem by removing the section of code that gets the current mapID and spawned 3000 trees into the grid that would effect the outcome of the path, without checking the current ID that path finding was able to handle multiple zombies on the full map with trees at about 56 fps.

However I noticed that zombies were able to move through barricades, which isn't supposed to be possible with the current code so i'll have to investigate it some more.
Was This Post Helpful? 0
  • +
  • -

#4 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 1
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Astar Path finding in large tile based worlds.

Posted 22 February 2012 - 04:58 PM

Every game developer is ultimately self-taught! the key is to know how to research and apply that knowledge to the appropriate situation. :)
Was This Post Helpful? 0
  • +
  • -

#5 hawksprite  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 7
  • View blog
  • Posts: 137
  • Joined: 11-September 09

Re: Astar Path finding in large tile based worlds.

Posted 22 February 2012 - 05:11 PM

Thanks for the advice, i'm reading about BSP now. I think I grasp the concept, now i'll have to figure out a fluid way to implement it into the grid.
Was This Post Helpful? 0
  • +
  • -

#6 hawksprite  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 7
  • View blog
  • Posts: 137
  • Joined: 11-September 09

Re: Astar Path finding in large tile based worlds.

Posted 22 February 2012 - 06:14 PM

I wasn't able to implement BSP but I did end up settling on a type of "tree" that fits into my grid for collision purposes. I'll post the class below.

 public class TreeHolder
    {
        public List<Region> parentRegions = new List<Region>();
        public int parentRegionSwitch(Vector2 Location)
        {
            // Return what region that location is in
            int id = -1;

            int ticker = 0;
            foreach (Region parent in parentRegions)
            {
                if (parent.InRegion(Location))
                    id = ticker;

                ticker++;
            }

            return id;
        }
        public int[] findTree(Vector2 Location)
        {
            int[] response = new int[2];
            // Get the parent region
            response[0] = parentRegionSwitch(Location);
            // Now find the child
            response[1] = parentRegions[response[0]].getChildID(Location);

            // Return the array of regions
            return response;
        }
        private Grid grid;

        public TreeHolder(Grid parentGrid)
        {
            grid = parentGrid;

            // The higher this is the more the children regions inside the parent regions will be broken down
            float childNodeCount = 50;

            // Convert the grid into a tree
            float masterWidth = parentGrid.Width / 2;
            float masterHeight = parentGrid.Height / 2;

            // Add the 4 parent regions
            //    1   |    2
            // ----------------
            //    3   |    4

            parentRegions.Add(new Region(Vector2.Zero, new Vector2(masterWidth, masterHeight), masterWidth));
            parentRegions.Add(new Region(new Vector2(masterWidth + 1, 0), new Vector2(masterWidth * 2, masterHeight), masterWidth));
            parentRegions.Add(new Region(new Vector2(0, masterHeight + 1), new Vector2(masterWidth, masterHeight * 2), masterWidth));
            parentRegions.Add(new Region(new Vector2(masterWidth + 1, masterHeight + 1), new Vector2(masterWidth * 2, masterHeight * 2), masterWidth));

            // render each parent region
            // Find the height and width counters for the children
            float width_counter = masterWidth / childNodeCount;
            float height_counter = masterHeight / childNodeCount;
            for (int i = 0; i < parentRegions.Count; i++)
            {
                parentRegions[i].setupChildren(width_counter, height_counter);
            }

            // Now that the tree is formed over the grid, go through the given grid and inject all the occupied points
            for (int i = 0; i < grid.occupiedPieces.Count; i++)
            {
                // Use the injector, this can also be used for when future objects are added to the map and need to be entered into the tree
                injectGridPece(grid.occupiedPieces[i]);
            }
        }

        public void injectGridPece(int id)
        {
            // Set this grid id as occupied, so find what region it's in and add it to the occupied list for that region
            Vector2 Location = grid.grid[id].Location;

            // Useing this location find what region it's in
            int[] regionHolder = findTree(Location);

            // Now inject the given id into the occupied list of the found region
            parentRegions[regionHolder[0]].children[regionHolder[1]].occupiedPieces.Add(id);
        }
    }

    public class Region
    {
        public Vector2 Min;
        public Vector2 Max;
        public float Size;

        public bool InRegion(Vector2 Location)
        {
            return Global.InRange(Min, Max, Location);
        }

        public Region(Vector2 _Min, Vector2 _Max, float size)
        {
            // Set the variables
            Min = _Min;
            Max = _Max;

            Size = size;
        }

        public List<Region> children = new List<Region>();
        public int getChildID(Vector2 Location)
        {
            // Check for the id through the children regions
            int id = -1;

            for (int i = 0; i < children.Count; i++)
            {
                if (children[i].InRegion(Location))
                    id = i;
            }

            return id;
        }

        public void setupChildren(float width_counter, float height_counter)
        {
            // The width_counter and height_counter tell this method how many tiles to add, by useing the parent region size and the counters you can get the height and width of the children regions
            float width = Size / width_counter;
            float height = Size / height_counter;

            for (int x = 0; x < width_counter; x++)
            {
                for (int y = 0; y < height_counter; y++)
                {
                    // Get the top left Corner of this region
                    Vector2 tLeft = new Vector2(x * width, y * height);
                    // The top left is also the min, so the max would perportion to the bottom right
                    Vector2 bRight = new Vector2((x * width) + width, (y * height) + height);

                    // Setup a region, then add it to the children list
                    children.Add(new Region(tLeft, bRight, width));
                }
            }
        }

        public List<int> occupiedPieces = new List<int>();
    }


Was This Post Helpful? 0
  • +
  • -

#7 hawksprite  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 7
  • View blog
  • Posts: 137
  • Joined: 11-September 09

Re: Astar Path finding in large tile based worlds.

Posted 22 February 2012 - 07:49 PM

After finalizing the tree that i placed over the grid and modified it further it still has spikes of crippling lag. I still think i'm doing something wrong.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1