Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Multiple pathfinders and memory usage  (Read 10472 times)
0 Members and 1 Guest are viewing this topic.
Offline appel

JGO Wizard


Medals: 49
Projects: 4


I always win!


« Posted 2007-12-13 23:32:24 »

Hey

I'm planning on using A* for pathfinding in my (next) game. I've already implemented it before (so I have full understanding of it), but there is one thing that I don't know how to solve and it's not really related to A* directly.

Since my game is going to be a RTS-kind, there may be multiple units trying to find a path, so I'm going to have a pool of let's say 3-5 pathfinder threads ready to find a path for any of those units in the game (async.)

Now, the way I implemented A* before was in a tile based grid;
- Each tile was represented by a node, and each node had a list of it's neighbors.
- So once I knew the start and goal nodes I could easily expand the search area by retrieving the neighboring nodes. (straight-forward!)
- However, it is only possible to execute one pathfinding operation at a time on the same set of nodes. This is because I use the nodes, define values in them, like if the node is "visited", the "parent" node, and the costs (estimated and totalfromstart).

How can I have more than 1 pathfinding thread searching in the same set of data (nodes) at the same time without duplicating all the nodes for each pathfinder?

Hopefully my question is making sense.


Also, tips on how to best implement a PathfindingResourcePoolManger are welcome Smiley

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline SimonH
« Reply #1 - Posted 2007-12-14 06:18:37 »

Simple answer; Don't have one node per tile. Keep a stack of nodes. The thing following the path only needs to know the actual path, so your pathfinding routine can discard useless nodes after the path is found. In other words; separate the pathfinding from the map. Depending on the complexity of the map this method should use less memory too...

People make games and games make people
Offline appel

JGO Wizard


Medals: 49
Projects: 4


I always win!


« Reply #2 - Posted 2007-12-14 14:31:30 »

Hey

Yes, I do seperate the pathfinding grid nodes from the map tiles. That is, I might have a int[ ][ ] array for the map and a Node[ ][ ] array for pathfinding.

However, would I need to duplicate the Node[ ][ ] array for each pathfinder? I don't like it, but hm... what do you mean by a "Stack of nodes"?

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline VeaR

Junior Member





« Reply #3 - Posted 2007-12-14 18:23:44 »

The way I've done it (a year ago) was to have Node and PathElement. Each PathElement contains the reference to a Node and the data specific to calculating the given path. After the Path was not needed any more, the PathElement objects were put back into and array, and reused when constructing another path.
Offline appel

JGO Wizard


Medals: 49
Projects: 4


I always win!


« Reply #4 - Posted 2007-12-14 18:38:06 »

The way I've done it (a year ago) was to have Node and PathElement. Each PathElement contains the reference to a Node and the data specific to calculating the given path. After the Path was not needed any more, the PathElement objects were put back into and array, and reused when constructing another path.

But in worst cases you'll need the same same number of PathElements for a Pathfinder as there are Nodes in the map, so it really defeats the purpose, might as well just use and duplicate the Nodes for each Pathfinder.

Example; if you try to find a path that does not exist, e.g. the goal node is trapped, then you might need to explore ALL nodes that are accessible from the start node.
Imagine a tilemap grid where all tiles are passable, except the goal tile is located in one corner and is enclosed by 3 blocking tiles. You would need to explore all the tiles except those 4.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline VeaR

Junior Member





« Reply #5 - Posted 2007-12-14 21:23:39 »

You can create a copy of the nodes if the size is manageable, but there are some other strategies:

Maintain sets of interconnected nodes, so with one single check you can make sure that a path exists. If all the nodes are interconnected, there will be only one set.
Limit the depth of the search. I had about 20K nodes, and the search was limited to 10K nodes. The reasoning was: if it takes a so complicated route to get there, the game situation will change so much, that the AI will need to do something else anyway.
The good thing in A* is that it can provide the closest node to target, no matter if the target is unreachable.
I allowed paths which didn't get to the target, but were close enough to "see" the target.
Offline SimonH
« Reply #6 - Posted 2007-12-14 21:26:04 »

what do you mean by a "Stack of nodes"?

I mean don't use arrays but Lists. Take a look here

People make games and games make people
Offline appel

JGO Wizard


Medals: 49
Projects: 4


I always win!


« Reply #7 - Posted 2007-12-15 00:11:42 »

Hey SimonH

I've been doing very similar as in that tutorial, however that tutorial only allows for one pathfinder at a time working on the set of nodes.

The way I've created the nodes for the pathfinding is:
1. Create the two-dimensional tilemap, e.g. Tiles[128][128] - this is not used in the pathfinding
2. Now I create a two-dimensional array of Node[128][128], e.g. Node [10][20] represents Tile[10][20].  - these nodes I'm going to use in the pathfinding.
3. Once the Node array has been created I loop through it, and for every node in the array I create a List of all it's neighbours (adjacent and diagonal to that node). I simply do something like: neighbour.add(nodes[x-1][y-1]) etc.
4. Now all nodes have their neighbours defined.

The above has several cons I've discovered:
1. Memory consuming, although it's ok for 1 pathfinder, it's probably not so good if I have multiple pathfinders. There must be a better way than to have 5 x Node[128][128] for 5 x pathfinders.
2. My game allows for diagonal movement, and I want the cost of diagonal movement to be larger than adjacent movement. This complicates things, now I need to know the physical location of the nodes, or at least how that node it attached, either adjacentally or diagonally, in order to calculate the correct cost.


I'd like to keep my pathfinder very general, so I can feed into it whatever start and goal nodes without it worrying about their physical locations (e.g. x and y). Not sure how calculating diagonal/adjacent cost fits into this idea.

Anyway, hopefully this explains my problem a bit better.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline SimonH
« Reply #8 - Posted 2007-12-15 03:35:15 »

My point is that you don't need the Node[][] array - the map tells you where you can and can't go

Here's my (fairly generic) a* code;

NB for diagonal moves modify the '+1' in getNeighbours() to '+sqrt(2)' to add to the cost

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
public class PathNode
{
   int x;
   int y;
   double cost;
   double dist;
   PathNode parent = null;

   public PathNode(int xIn, int yIn, double costIn, double distIn) {
      x = xIn;
      y = yIn;
      cost = costIn;
      dist = distIn;
   }
}

/******************************************************************
 * getNeighbours
 * function used in pathfinding
 ******************************************************************/

   private Vector getNeighbours(int x, int y, double cost, int tx, int ty) {
      Vector list = new Vector();
      for (int dx=-1; dx<2; dx++)
      {
         for (int dy=-1; dy<2; dy++)
         {
            if ((dx != 0) || (dy != 0))
            {
               if ((x+dx>-1) && (x+dx<gridWidth) && (y+dy>-1) && (y+dy<gridHeight))
               {
                  int content=readMap(x+dx,y+dy);
                  if (content==EMPTY) // if empty
                 {
                     double dist = range(x, y, tx, ty);
                     list.addElement(new PathNode(x + dx, y + dy, cost + 1, dist));
                  }
               }
            }
         }
      }
      return list;
   }
/******************************************************************
 * removeFromList
 * function used in pathfinding
 ******************************************************************/

   private void removeFromList(Vector v, PathNode p) {
      Enumeration e = v.elements();
      while (e.hasMoreElements()) {
         PathNode nn = (PathNode) e.nextElement();
         if ((nn.x == p.x) && (nn.y == p.y)) {
            v.removeElement(nn);
            return;
         }
      }
   }
/******************************************************************
 * addToOpen
 * function used in pathfinding
 ******************************************************************/

   private void addToOpen(Vector open, int x, int y, double cost, double dist, PathNode parent) {
      PathNode node = new PathNode(x, y, cost, dist);
      node.parent = parent;
      if (open.size() > 0) {
         for (int i=0; i<open.size(); i++) {
            PathNode p = (PathNode) open.elementAt(i);
            if (p.cost > cost) {
               open.insertElementAt(node, i);
               return;
            }
         }
      }
      open.addElement(node);
   }
/******************************************************************
 * checkIfGot
 * function used in pathfinding to avoid duplication of squares
 ******************************************************************/

   private boolean checkIfGot(Vector v, PathNode p) {
      Enumeration e = v.elements();
      while (e.hasMoreElements()) {
         PathNode nn = (PathNode) e.nextElement();
         if ((nn.x == p.x) && (nn.y == p.y)) return true;
      }
      return false;
   }
/******************************************************************
 * findPath
 * entry function used in pathfinding
 ******************************************************************/

   public Vector findPath(int sx, int sy, int tx, int ty) {

      Vector path = new Vector();
      Vector open = new Vector();
      Vector closed = new Vector();

      int count = 0;

      if ((sx == tx) && (sy == ty)) {
         path.insertElementAt(new PathNode(tx, ty, 0, 0), 0);
         return path;
      }

      double dist = range(sx, sy, tx, ty);
      addToOpen(open, sx, sy, 0, dist, null);

      while (!open.isEmpty())
      {
         PathNode pn = (PathNode) open.elementAt(0);
         open.removeElementAt(0);
         if ((pn.x == tx) && (pn.y == ty)) {
            // path found
           while (pn.parent != null)
            {
               path.insertElementAt(pn, 0);
               pn = pn.parent;
            }
            return path;
         }
         // get neighbours
        Vector neighbours = getNeighbours(pn.x, pn.y, pn.cost, tx, ty);
         count++;
         // check each neighbour
        Enumeration e = neighbours.elements();
         while (e.hasMoreElements())
         {
            PathNode nn = (PathNode) e.nextElement();
            // check if in open & closed
           boolean isInOpen = checkIfGot(open, nn);
            boolean isInClosed = checkIfGot(closed, nn);

            double cost = pn.cost + range(pn.x, pn.y, nn.x, nn.y);

            if ((!isInOpen) && (!isInClosed) || (cost < nn.cost)) {
               nn.parent = pn;
               nn.cost = cost;
               if (isInClosed) removeFromList(closed, nn);
               addToOpen(open, nn.x, nn.y, nn.cost, nn.dist, nn.parent);
            }
         }
         closed.addElement(pn);
      }
      return null;
   }

People make games and games make people
Offline appel

JGO Wizard


Medals: 49
Projects: 4


I always win!


« Reply #9 - Posted 2007-12-15 07:16:29 »

Thanks for your code.

But I raise both of my eyebrows when I read it.

First, your A* is very dependant upon knowing it's surroundings. I feel this is not what A* is supposed to know, sort of like cheating Smiley. What if you had a regular graph of nodes, e.g. where nodes can have anywhere from 1 to 10 neighbours (or more!). I'm not saying your method is wrong, but I'm creating a pathfinding package that is supposed to be *abstract* enough for both uses.
E.g., your A* wouldn't work on hexagonal grid where each tile has 6 neighbours instead of 8.

Second, holy holy!! Your getNeighbours(...) method is a HUGE performance bottleneck. I've implemented A* that way before, and it's anywhere from 10-20 times slower than using a pre-existing nodes. Not to mention GC overhead because of all those "new's". Also, in those worst-case scenarios I talked about you might need to create just as many PathNode's as there are tiles on the map (subtracting 3). You could never use this in a proper computer game where you might have hundreds, or even dozens, of entities requesting path every minute or so.

Third, your methods "checkIfGot()" and "removeFromList()" are both O(n), which is not optimal. These should be O(1) IMO, if you want your A* to be quick.

Fourth, I'm not sure, but I'm not confident in your cost calculations.
You seem to do "double cost = pn.cost + range(pn.x, pn.y, nn.x, nn.y);" for calculating the cost from the start. This doesn't consider that tiles can have different cost, e.g. hill tile vs. road tile where the tank should avoid the hill tile. Also, I find it strange that you need to do euclidean distance calculation between two adjacent tiles! This can be easily fixed though, and I'm sure your A* implementation works fine without this.


In a way your A* implementation *does* solve my multithreading problem, but it however introduces many bad things.


Hopefully my comments are well taken Smiley

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline SimonH
« Reply #10 - Posted 2007-12-15 14:20:22 »

But I raise both of my eyebrows when I read it.

Sorry, Sir! I'll do it again only better! Wink

This was written ages ago for an app where code legibility was more important than speed (that's why I posted it!).
It's not that dependent on surroundings though - the getNeighbours() function is all that needs changing...
I agree that it can be vastly imporved, but the important thing is the separation between the map and the pathfinding code.



People make games and games make people
Offline appel

JGO Wizard


Medals: 49
Projects: 4


I always win!


« Reply #11 - Posted 2007-12-16 21:44:31 »

nm, I've decided this is more trouble than it's worth. I'll just make my pathfinder and make if a 2D grid specific.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline raft

Senior Newbie




aptalkarga.com


« Reply #12 - Posted 2008-03-21 17:09:51 »

it has been months since you posted this, but here is my 2 cents.. 

- However, it is only possible to execute one pathfinding operation at a time on the same set of nodes. This is because I use the nodes, define values in them, like if the node is "visited", the "parent" node, and the costs (estimated and totalfromstart).
i do the same in my A* implementation too. that's a good thing for performance IMHO.

How can I have more than 1 pathfinding thread searching in the same set of data (nodes) at the same time without duplicating all the nodes for each pathfinder?
my short answer is dont Wink why do you need spreading pathfinding amoung multiple threads ? more threads wont give you any more cpu time. they're mostly useful to parallelize blocking operations like i/o. it's true you can benefit from dual-core cpu's by spawning a thread for pathfinding but even in that case one pathfinding thread will be enough. just queue the pathfind requests in that thread

but, if you really really want to spawn a thread for each pathfind request, you need to decouple A* information from your nodes: that is, move f, g, h and parent fields from node to another class (say NodeAData) and some how lookup for them. if each of your nodes has a unique id, you may put them into a HashMap or so (and face the lookup performance issues Wink). or assigning an id to each pathfind request, and allow your nodes to hold more than one NodeAData maybe another option. this will reduce the lookup time, but you will need to clean them later

hope this helps,
r a f t

Offline DzzD
« Reply #13 - Posted 2008-03-21 18:06:16 »

cant you try the solution I told about there ?

http://www.java-gaming.org/forums/index.php?topic=17924.0

I mean using a temporal dimension ? as if you were using a 3D array rather than a 2d Array with third dimendion representing turn/time, one unit can only be in one 2d pos for a given 3d/temporal index this way you do not have to make parrallel path search. but just a 3 dimension path finder once an unit find a path, this path is stamped as occupied than you find for unit two, than unit three, etc...

Offline raft

Senior Newbie




aptalkarga.com


« Reply #14 - Posted 2008-03-21 18:35:45 »

cant you try the solution I told about there ?

http://www.java-gaming.org/forums/index.php?topic=17924.0

I mean using a temporal dimension ? as if you were using a 3D array rather than a 2d Array with third dimendion representing turn/time, one unit can only be in one 2d pos for a given 3d/temporal index this way you do not have to make parrallel path search. but just a 3 dimension path finder once an unit find a path, this path is stamped as occupied than you find for unit two, than unit three, etc...

you are talking about cooperative pathfinding. but as described in that paper, if you only add a 3rd dimension as time to your search space and use same heuristic as before, you will run into performance issues (possibly not noticable for small maps) you need some other heuristic like that true distance heuristic feeded by reverse A* search. in that case I argue that it's simple to implement

Offline appel

JGO Wizard


Medals: 49
Projects: 4


I always win!


« Reply #15 - Posted 2008-04-03 00:09:30 »

I've discovered that it is sufficient to run one pathfinder in a thread, on recent computers there is no fps drop.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline JAW

Senior Member


Medals: 2



« Reply #16 - Posted 2008-05-09 15:40:20 »

There has been said a lot already, I might repeat some but I must admit I didnt read everything:

1) Finding 5 paths the same time would actually not be faster than finding 5 paths sequentially. The CPU has the same amount of work to do, plus thread scheduling. Concurrent threads would give you an advance, when you have one big and one small search, the small one would be done soon and does not have to wait for the big one.

2) Pathfinding information does NOT belong to the node. Either you keep a visited list with nodes, or you use a PathFindingNode object which keeps reference to a node. Both ways, you can use map nodes concurrently.

3) Groups of units can share a pathfinding. Either all use the same path or you move the path of each one by its distance to the starting cell of o the search. But it can happen that a moved path runs into an obstacle, so you must check and correct such paths, but its still cheaper than searching again.

-JAW
Offline j2me_beginner

Junior Newbie





« Reply #17 - Posted 2010-04-01 10:51:40 »

Hi, I like to know how to create logic for a weapon in the game which should not make a close circuit while place it on the game screen.
Its like there are (x,y) number of rows and columns. The user is allowed to place the weapon on the screen. The screen looks like a chess board. Full of odd number of rows and columns in the shape of squares.
Now the user can place the weapon on these squares so that as and when the enemies come they detect using collusion and the if its on firing range they fire to the enemy.
So now the weapon can be placed such that it should not form a closed circuit, that is it should leave one square empty so that the enemy moves out.
The enemy has a start state and a goal state. And it moves in the form of elephant of a chess game.
The enemy starts from say suppose top of a screen and moves one one square and doj's the weapon and reaches other end of the screen.
SO i like to know how to stop the weapon from making a closed circuit?

In all total there are 9 columns and 11 rows, in all total 99 squares of 24 x 24 ok.
Weapons are places inside the squares. But it should not make a close circuit. Means I cannot block the whole row full of weapons. Say there should be a 24 x 24 cell left for the enemy to move around.

If i create a square or rectangle ,I should leave a 24 x 24 cell left so that the enemy passes through, from start state to the goal state.

For enemies I use A* algo. but for placing the weapons................dont know how.

The game is like iphone field runner. Kindly see the video in youtube and see how the weapons are placed and help me.
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #18 - Posted 2010-04-01 11:38:01 »

Please stop spamming the forum with the same question. Nate has already given you the answer.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

ctomni231 (35 views)
2014-07-18 06:55:21

Zero Volt (31 views)
2014-07-17 23:47:54

danieldean (26 views)
2014-07-17 23:41:23

MustardPeter (28 views)
2014-07-16 23:30:00

Cero (43 views)
2014-07-16 00:42:17

Riven (45 views)
2014-07-14 18:02:53

OpenGLShaders (34 views)
2014-07-14 16:23:47

Riven (35 views)
2014-07-14 11:51:35

quew8 (31 views)
2014-07-13 13:57:52

SHC (67 views)
2014-07-12 17:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!