Databases
StackOverflow2013
Postsdbo
POA Star Pathfinding Algorithm Heuristic for Cube Surface
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POA Star Pathfinding Algorithm Heuristic for Cube Surface
    primarykey
    data
    text
    <p>I'm building a <a href="http://mhluska.com/demo/snake3d" rel="nofollow">snake game</a> that plays on the surface of a cube. Currently it uses Dijkstra's algorithm for pathfinding. Despite optimizations with set and priority queue data structures, it is still a bit too slow. You notice the delay when the snake eats a food item and begins searching for a new one.</p> <p>I'm trying to get it to use A* instead but I can't find a good heuristic. On a flat grid with 4 directions of movement, I would use Manhattan distance. I've tried using 3D Manhattan distance <code>abs(dx) + abs(dy) + abs(dz)</code> which didn't work for good reason: to the snake, the game world is really <a href="http://www.bbc.co.uk/schools/ks3bitesize/maths/images/net_of_a_cube.gif" rel="nofollow">6 grids (corresponding to the faces of the cube)</a> with unusual wrap-around properties.</p> <p>In the code, each square is stored in a <code>grid[15][15]</code> 2D array. There are 6 such arrays to store each face. So each square has an <code>(arrayX, arrayY, d)</code> triple to describe the offset in the 2D array and specify which array. Also, each square has an <code>(x, y, z)</code> triple describing spatial position.</p> <p>Here's the area of game code where the pathfinding happens: </p> <p><a href="https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105" rel="nofollow">https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105</a></p> <p>Here's the library code for A*:</p> <p><a href="https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60" rel="nofollow">https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60</a></p> <p>What is a suitable, concise heuristic for this game world?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMaros Hluska
    1. USMaros Hluska
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POA Star Pathfinding Algorithm Heuristic for Cube Surface
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POA Star Pathfinding Algorithm Heuristic for Cube Surface
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POA Star Pathfinding Algorithm Heuristic for Cube Surface
      1. USsampson-chen
      1. VTFavorite
    1. COYou can think of your graph as a 2D + shaped grid that wraps around, so your heuriistic for A* would just be taking taking the minimum of a few values *(try to imagine how you'd do it on a 1D grid that wraps around first)*. However, with only 1000 nodes, this really shouldn't be necessary, even in Javascript. Some part of your code (or perhaps the data-structures you use) is taking **way** too long to run. You need to do some profiling, to determine which lines are causing the slowdown - you should easily be able to search over 1000 nodes without a noticable delay.
      singulars
      1. POA Star Pathfinding Algorithm Heuristic for Cube Surface
      1. USBlueRaja - Danny Pflughoeft
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload