Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (581) Games in Android Showcase (163) games submitted by our members Games in WIP (632) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 About the darned grid, collisions and pathfinding  (Read 2179 times) 0 Members and 1 Guest are viewing this topic.

JGO Ninja

Medals: 26
Projects: 3
Exp: 6 years

One for all!

 « Posted 2012-08-13 15:17:02 »

Hello!

I've known for awhile that it's better to index everything into a giant grid and then query said grid for entities, than querying the entire world.
I do have a few questions left unanswered, and I hope some of you can shed light on this.

I’ve tried to write this in an understandable way, and I even provide some illustrations.

A perfect situation of querying a grid, would be this:

The circle represents your entity, and it should be clear that the entity is indeed in cell (1, 1).

It’s easy to ask (in code) “Hey! Is anything in the way, over at (1, 1)”, and it’s easy to find out that the circle is there.

Consider this next scenario:

The circle is the same. It still fits within one square, but it’s not entirely inside a single square. This scenario is possible within a ton of games, but how do we handle it?
What cell is it actually inside? If we decide that it’s still (1, 1), then what happens if we need to check if there are no collisions in cell (2, 1)? Obviously the outcome isn’t great, because the game won’t recognize anything in the (2, 1) area.

Here’s an actual question: With the above in mind, do I want duplicate entries in the grid? If yes, I no longer have to worry about -||-
I always thought that I didn’t want duplicate entries, and so I’ve had a few thoughts on how to handle the problem.

Here’s one: I can query multiple cells, based on how big my entities are.
Let’s say that my largest entity, is equal to the size of the blue circle:

Now, if I want to query cell (3, 3), I need to do it like this:

Because my largest entity can leak over 9 cell, I need to query the 8 cell around the starting point to make sure I don’t miss anything (provided that there is only one entry of each entity). That makes performance a lot worse.

Is there any ways around this problem? Is there an easy way to find out what cells an entity is touching, if the entities center vector, and radius is available?

Also, how is pathfinding in an environment like this possible? I would make targets at the center of each cell, and just use the heuristic to get my entity there. That makes it easy to apply A* for instance. However, that way it can easily become difficult to find a valid path.
I don’t want to avoid a cell, just because the edge of an entity is slightly leaking into it. That doesn’t pose an actual obstacle, especially if the mover is a much smaller circle, that can easily maneuver past the edge of the leaking entity, without leaving the cell. I’ve illustrated this below.

Another thing is, how does one query collisions accurately, in this environment? Say, I want to know whether a small circle is intersecting with anything, but it’s radius is a cell’s width 1/20 (like a bullet in a game).

For completely practical reasons: How big should each cell be? Not too small because it’ll be slower, but not too big either. Is there any general rule of thumb, like equal to the size of my smallest entity?

I know a bunch of you have been working with an environment like this, so please enlighten me.

Thanks a ton.

sproingie

JGO Kernel

Medals: 202

 « Reply #1 - Posted 2012-08-13 15:28:52 »

An entity that spans multiple cells is in all of them.  Finding out which cells an entity touches is as simple as making a bounding box around it -- this should be pretty trivial for circles.  This will result in some false positives on corners, but the idea isn't for an exact position, it's just to narrow down the list of entities you do more precise comparisons with.

A cell should be "big enough" to partition your space so that most cells contain only one or two objects, but that you're not wasting space with empty cells between objects or having to inhabit several cells for every entity.  You should consider dynamically adjusting it and benchmarking to see which arrangement fits best.
UprightPath
 « Reply #2 - Posted 2012-08-13 16:13:23 »

Big question: What sort of game will this be for? If it's a platformer, then there will be slightly different rules for how you design the node-set for your game (Pathfinding it is about the same, however). If it's for something that's relatively top-down, or where movement occurs unit by unit and only in strict compass directions (N-NE-E-SE-S-SW-W-NW) or something similiar, then your grid can be used for pathfinding.

Either way, a lot deals with how your movement rules work. Here are some things to consider (Which weren't made too obvious by your post that you should think about. Sorry if I'm just not understanding your intention and mentioning things you felt answered!)

0) Are movements/positions going to be grid-aligned at all?
1) How do entities move? Platform: Do jumps have a calculable height/distance that they can typically be expected to attain, are there different 'rules' for walking across different spaces, etc. Actual Grid:  Is it a single 'step' per turn (Think a rogue like) or is do they have a moment range (Think Final Fantasy Tactics) per turn?
2) Decide whether entities can coexist on a given grid square. If it's a strict no then this makes things pretty straight forward. If it's a yes then you need to decide how you're going to handle overlaps and the like.
3) Like Sprongie said, your grid should be just the right size. Selecting the smallest entity that you possess and using that to designate your grid side could work, or a grid square that is the smallest possible movement distance per turn. This one depends on question 1, in that you'll have some sort of trade off. If you select the grid by entity, but you have movement increments smaller than that, you'll end up having an entity straddling several squares that way. If you select the grid by movement, but your units are all bigger than the smallest unit, then all units will straddle several squares simply due to size.

Why are these important?
Number of Paths Needed: Depending on how your movement system works, your entities are likely going to have to use the pathfinder quite a few times, perhaps as often as once per turn. For 'Step' method this is mainly to do with passable squares becoming impassable (See question 2) and can result in a form of thrashing (Think when you're walking towards someone and you both step to the side to let the other pass). For the 'range' you'll typically still end up needing to find paths as often, however the chance of the thrash mentioned above is less likely.
Path accuracy: Depending on how you're handling overlap, you can end up with lots of sub-optimal paths (Which typically aren't too much of an issue). This can get better/worse if you only find a new path when there's an interruption on the current one or when you change targets.

jonjava
 « Reply #3 - Posted 2012-08-13 17:15:57 »

Shouldn't this be accomplished with the exact method you linked to in an earlier collision problem?

http://www.java-gaming.org/topics/platformer-collision-help-reducing-comparisons/27039/msg/240686/view.html#msg240686

If an object overlaps grids, check its collision against all the objects in those grids.

[EDIT]:
Here's another more articulate and concise link for the same thing: http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/

JGO Ninja

Medals: 26
Projects: 3
Exp: 6 years

One for all!

 « Reply #4 - Posted 2012-08-13 18:24:44 »

Shouldn't this be accomplished with the exact method you linked to in an earlier collision problem?

http://www.java-gaming.org/topics/platformer-collision-help-reducing-comparisons/27039/msg/240686/view.html#msg240686

If an object overlaps grids, check its collision against all the objects in those grids.

Indeed, but there are still a few things left unanswered, like the pathfinding. I've come to the realization that entities that are in multiple cells, are added to each cells list.

Either way, a lot deals with how your movement rules work. Here are some things to consider (Which weren't made too obvious by your post that you should think about. Sorry if I'm just not understanding your intention and mentioning things you felt answered!)

0) Are movements/positions going to be grid-aligned at all?

You nailed it, and I admit I left out on quite a few things. I'm going to let you imagine how movement works for "TLOZ: A Link To The Past", and assume you know your classics
Each entity is not blocking (In Zelda it was only imaginary because Link jumps back), and they are not aligned to the grid. They move completely independently of the grid, and eachother (in theory - I can still do a BB-overlap test, within the cell).
I thought I could make pathfinding work with the cells though (imagine the cell size as big as the tiles in Zelda), and just use trig to guide an entity towards the middle of each tile/node, until the node is reached. Then proceed to the next node. This should work great, but it doesn't take into account other entities. It'll just check whether or not a tile is occupied, and it could be occupied by just the nosetip of some skeleton, which is inaccurate if the entity is small enough. Else, I can disregard entities, but then I can't have any collidable entities. I'd like to have that, since I might have boulders and other things to interract with.

princec

« JGO Spiffy Duke »

Medals: 506
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #5 - Posted 2012-08-13 18:45:49 »

Here's the collision manager I use. Notice how collisions are processed - each pair is notified an an arbitrary order of the collision. Make sure you understand that bit.

 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  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  201  202  203  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  219  220  221  222  223  224  225  226  227  228  229  230  231  232  233  234  235  236  237  238  239  240  241  242  243  244  245  246  247  248  249  250  251  252  253  254  255  256  257  258  259  260  261  262  263  264  265  266  267  268  269  270  271  272  273  274  275  276  277  278  279  280  281  282  283  284  285  286  287  288  289  290  291  292  293  294  295  296  297  298  299  300  301  302  303  304  305  306  307  308  309  310  311  312  313  314  315  316  317  318  319  320  321  322  323  324  325  326  327  328  329  330  331  332  333  334  335  336  337  338  339  340  341  342  343  344  345  346  347  348  349  350  351  352  353  354  355  356  357  358  359  360  361  362  363  364  365  366  367  368  369  370  371  372 `/* * Copyright (c) 2003-onwards Shaven Puppy Ltd * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * * Redistributions of source code must retain the above copyright *   notice, this list of conditions and the following disclaimer. * * * Redistributions in binary form must reproduce the above copyright *   notice, this list of conditions and the following disclaimer in the *   documentation and/or other materials provided with the distribution. * * * Neither the name of 'Shaven Puppy' nor the names of its contributors *   may be used to endorse or promote products derived from this software *   without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */package puppytron;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;import org.lwjgl.util.ReadableRectangle;import org.lwjgl.util.Rectangle;/** * Grid-based collision manager. */class GridCollisionManager implements CollisionManager {   private static final int INITIAL_ENTITIES = 512;   private static final int BORDER_TILES = 4;   private static class Cell {      final ArrayList contents = new ArrayList(4);      boolean inUsed;   }   private static class Pair {      Entity a, b;      Pair(Entity a, Entity b) {           this.a = a;           this.b = b;        }      @Override      public int hashCode() {          return a.hashCode() + b.hashCode();      }      @Override      public boolean equals(Object obj) {         Pair p = (Pair) obj;         return ((p.a == a && p.b == b) || (p.a == b && p.b == a));      }   }   /** Temp pair */   private final Pair tempPair = new Pair(null, null);   /** Temp rects */   private final Rectangle temp = new Rectangle(), cells = new Rectangle();   /** Collision pairs */   private final List collisions = new ArrayList();   /** Cell size */   private final int cellSize;   /** Bounds, in a rectangle */   private final ReadableRectangle mapBounds;   /** The sparse grid */   private Cell[] grid;   /** All cells which actually contain at least 1 entity */   private ArrayList used = new ArrayList(INITIAL_ENTITIES), used0 = new ArrayList(INITIAL_ENTITIES);   /** Origin (grid) */   private int ox, oy;   /** Size (grid) */   private int w, h;   /** Map of Entities to ReadableRectangles; this maps Entities to the cells in which they have been placed */   private Map entityMap = new HashMap(INITIAL_ENTITIES);   private static int fastFloor(float x) {      int i = (int) x;      return x >= 0.0f ? i : i == x ? i : i - 1;   }    GridCollisionManager(int cellSize) {      this.cellSize = cellSize;      ox = -BORDER_TILES;      oy = -BORDER_TILES;      w = GameMap.SIZE + BORDER_TILES * 2;      h = GameMap.SIZE + BORDER_TILES * 2;      grid = new Cell[w * h];      mapBounds = new Rectangle(0, 0, w, h);   }   @Override   public void clear() {      Arrays.fill(grid, null);      used.clear();      entityMap.clear();   }//   public Rectangle test(Entity entity) {//      calcBounds(entity);//      return calcCells(temp, new Rectangle());//   }   @Override   public void store(Entity entity) {      // See which cells we should be in and maybe resize the grid      calcBounds(entity);      Rectangle r = calcCells(temp, new Rectangle());      if (entityMap.put(entity, r) != null) {         assert false : "Entity "+entity+" is already in the entityMap!";      }      // Add this entity to each cell//      assert r.getX() >= 0 : r+" "+temp+" "+entity;//      assert r.getY() >= 0 : r+" "+temp+" "+entity;//      assert r.getX() < w : r+" "+temp+" "+entity;//      assert r.getY() < h : r+" "+temp+" "+entity;//      assert r.getX() + r.getWidth() <= w : r+" "+temp+" "+entity;//      assert r.getY() + r.getHeight() <= h : r+" "+temp+" "+entity;      int cell = r.getX() + r.getY() * w;      for (int y = r.getHeight(); -- y >= 0; ) {         for (int x = r.getWidth(); -- x >= 0; ) {            try {               Cell c = grid[cell];               if (c == null) {                  c = new Cell();                  grid[cell] = c;               }               c.contents.add(entity);               if (!c.inUsed) {                  c.inUsed = true;                  used.add(c);               }            } catch (ArrayIndexOutOfBoundsException e) {               System.err.println(r+" "+cell);               e.printStackTrace();            }            cell ++;         }         cell += w - r.getWidth();      }   }   private void calcBounds(Entity entity) {      float radius = entity.getRadius();      assert radius >= 0.0f : entity+" has radius "+radius;      // it's a round entity - we'll expand its bounds a bit to account for freaky rounding      int size = (int)(radius * 2.0f) + 2;      temp.setBounds((int)(entity.getCollisionX() - radius) - 1, (int)(entity.getCollisionY() - radius) - 1, size, size);   }   public Rectangle calcCells(ReadableRectangle src, Rectangle dest) {      int x0 = fastFloor(src.getX() / (float) cellSize);      int y0 = fastFloor(src.getY() / (float) cellSize);      int x1 = fastFloor((src.getX() + src.getWidth() - 1) / (float) cellSize);      int y1 = fastFloor((src.getY() + src.getHeight() - 1) / (float) cellSize);      dest.setBounds         (            x0 - ox,            y0 - oy,            (x1 - x0) + 1,            (y1 - y0) + 1         );      Rectangle clipped = dest.intersection(mapBounds, dest);      dest.setBounds(clipped);      return clipped;   }   @Override   public CollisionManager add(Entity entity) {      store(entity);      return this;   }   @Override   public CollisionManager submit(ReadableRectangle rect) {      return this;   }   @Override   public boolean remove(Entity entity) {      // Shortcut: look in entity map first      ReadableRectangle existingCells = entityMap.remove(entity);      if (existingCells != null) {         int cell = existingCells.getX() + existingCells.getY() * w;         for (int yy = existingCells.getHeight(); -- yy >= 0; ) {            for (int xx = existingCells.getWidth(); -- xx >= 0; ) {               Cell test = grid[cell];               if (test == null) {                  assert false : "Entity "+entity+" was supposed to be at "+existingCells+" but isn't at "+(cell % w)+","+(cell / w);                  return false;               }               if (!test.contents.remove(entity)) {                  assert false : "Entity "+entity+" not found where it was expected!";               }               cell ++;            }            cell += w - existingCells.getWidth();         }         return true;      } else {         assert false : "Entity "+entity+" not found!";         return false;      }   }   @Override   public List checkCollisions(Entity entity, List dest) {      if (dest == null) {         dest = new ArrayList();      }      dest.clear();      if (!entity.isActive() || !entity.canCollide()) {         // Shortcut: src entity can't collide         return dest;      }      calcBounds(entity);      calcCells(temp, cells);      int cell = cells.getX() + cells.getY() * w;      for (int y = cells.getHeight(); -- y >= 0; ) {         for (int x = cells.getWidth(); -- x >= 0; ) {            Cell c = grid[cell];            if (c != null) {               List contents = c.contents;               final int n = contents.size();               for (int i = n; --i >= 0; ) {                  Entity test = contents.get(i);                  if (entity != test && test.isActive() && test.canCollide() && test.isTouching(entity) && !dest.contains(test)) {                     dest.add(test);                  }               }            }            cell ++;         }         cell += w - cells.getWidth();      }      collisions.clear();      return dest;   }   @Override   public List checkCollisions(ReadableRectangle rect, List dest) {      if (dest == null) {         dest = new ArrayList();      }      dest.clear();      calcCells(rect, cells);      int cell = cells.getX() + cells.getY() * w;      for (int y = cells.getHeight(); -- y >= 0; ) {         for (int x = cells.getWidth(); --x >= 0; ) {            Cell c = grid[cell];            if (c != null) {               List contents = c.contents;               final int n = contents.size();               for (int i = n; --i >= 0; ) {                  Entity entity = contents.get(i);                  if (entity.isActive() && entity.canCollide() && entity.isTouching(rect) && !dest.contains(entity)) {                     dest.add(entity);                  }               }            }            cell ++;         }         cell += w - cells.getWidth();      }      collisions.clear();      return dest;   }   @Override   public void checkCollisions() {      // For each cell with something in it...      for (int i = used.size(); --i >= 0; ) {         Cell cell = used.get(i);         if (cell.contents.size() > 0) {            used0.add(cell);         }      }      for (int cell = used0.size(); --cell >= 0; ) {         // Process all combinations within that cell         List contents = used0.get(cell).contents;         for (int i = 0; i < contents.size(); i ++) {            Entity src = contents.get(i);            if (src.isActive() && src.canCollide()) {               for (int j = i + 1; j < contents.size(); j ++) {                  Entity dest = contents.get(j);                  if (dest.isActive() && src.isActive() && src.canCollide() && dest.canCollide() && src.isTouching(dest)) {                     // Inform both entities of the collision, in no particular order, unless already done                     tempPair.a = src;                     tempPair.b = dest;                     if (collisions.contains(tempPair)) {                        continue;                     }                     collisions.add(new Pair(src, dest));                     src.onCollision(dest);                     dest.onCollision(src);                  }               }            }         }      }      // Compact used list      used0.clear();      for (int i = used.size(); --i >= 0; ) {         Cell cell = used.get(i);         if (cell.contents.size() > 0) {            used0.add(cell);         } else {            cell.inUsed = false;         }      }      ArrayList temp = used;      used = used0;      used0 = temp;      used0.clear();      // Clear away collisions now they're all processed      collisions.clear();   }}`

Cas

JGO Ninja

Medals: 26
Projects: 3
Exp: 6 years

One for all!

 « Reply #6 - Posted 2012-08-13 20:11:05 »

Thank you so much Cas, that will definitely come in handy. I do find that quite hard to look at, and it doesn't seem apparent which segments executes when.
I'm not sure I get the "pair" sentiment, and I'm definitely not going to resize my grid over any period of time just yet (I have little idea when to, and what sizes are desirable).

I want to understand your code, but I think a lot of understandability (In lack of a better word) went down the drain as performance improved (That's usually how it goes  ).

princec

« JGO Spiffy Duke »

Medals: 506
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #7 - Posted 2012-08-13 20:55:05 »

It's not exactly intended for public consumption but it might give you the gist of how you might implement it yourself That particular implementation assumes all entities are circular, and every time an entity is moved or its radius changes, you must remove() the entity and then store() it again. You call checkCollisions() once per tick to process all collisions, after all movement has taken place. There are a couple of other checkCollisions() methods to query the grid and return results as well.

Here's a bit of a blast from the past: Collision detection in Alien Flux

Cas

Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 MrMapcom (24 views) 2015-05-23 20:26:16 MrMapcom (31 views) 2015-05-23 20:23:34 Waterwolf (36 views) 2015-05-20 15:01:45 chrislo27 (44 views) 2015-05-20 03:42:21 BurntPizza (77 views) 2015-05-10 15:53:18 FrozenShade (61 views) 2015-05-07 09:11:21 TheLopais (226 views) 2015-05-06 13:36:48 TheLopais (207 views) 2015-05-06 13:35:14 TheLopais (213 views) 2015-05-06 13:33:39 TheLopais (234 views) 2015-05-06 13:32:48
 Spasi 32x Rayvolution 17x Riven 16x Drenius 15x BurntPizza 15x theagentd 14x ra4king 13x opiop65 12x EgonOlsen 11x princec 11x DavidBVal 11x Husk 11x KevinWorkman 9x scanevaro 8x orangepascal 8x SauronWatchesYou 8x
 List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00
 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