468,114 Members | 1,912 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,114 developers. It's quick & easy.

I Double Dare you: Write a shortest path process for a grid-layout game if you can.

SwissProgrammer
206 128KB
C and/or C++

Not Visual Basic. Not Visual C++. Not .NET . Just C or C++.

Let me see some real C or C++ code that does this.

{please and thank you if you feel like it}

And not some text based CLI output that pretends to work and looks like it might work and maybe works and bla bla bla, but does NOT work for a grid-based game.

Here are some grid background examples [X], [X]

Prove to me that you can write one in C or C++ that does what is shown on this [X] page. That is an animated gif on that page. That is NOT a working C or C++ example on that page. But you get the idea.




I have been studying some current and past games and doing some testing of them to see how they got this working.

SURPRISE ! I did NOT find ANY game that had a shortest path correctly working. They got close, but with testing I found errors in shortest paths.



I have found many examples of how to write a shortest path algorithm. NONE of those (NOT EVEN ONE!) of those tested out to be useful in a simply structured grid-layout game. A grid-layout game is about as simple as it gets for testing a shortest path algorithm and this did not work for it. Thus, if Dijkstra’s algorithm worked for Dijkstra that does not mean that it will work for anyone else that has a computer generated game that uses a grid layout.

If YOU have a shortest path process that works for a grid-layout type of game then please post it here on bytes.com as an article.

Or if you need a challenge, write one of these yourself. I dare you to try. Not just some pseudo-code. Some actual working code. I Double Dare you.

Thank you.
2 Weeks Ago #1
8 3847
Rabbit
12,510 Expert Mod 8TB
I don't program in C or C++ but it sounds like you can find working code for a graph but not one for a grid layout. A grid can be represented as a graph with edges to all orthogonal cells. So you could insert a step to convert the grid to a graph and then run the graph version of dijkstra's.
2 Weeks Ago #2
SwissProgrammer
206 128KB
Rabbit,

I tried that. Every example that I found and every way that I tried did not work for a grid (or graph) layout such as [X].

I have been struggling with this for over 6 months. Not all day every day but often. I work at it until I give up, then try again later. I tried pseudo code. I tried writing it out on paper each step and then tried to code that in. I have posted here on bytes.com some of my attempts that seemed to get close. None of these has worked so far. It seems to be a matter of logic converted to code.

The process should be simply an if then else process.

Try going to one grid square at a time. Add that result, if not blocked like at the edge or similar (with length or time) to a vector for comparison later. I know that. At this point, I can't seem to even code that in.

I can do it, but I can not do it.

It has to be basic simple logic. It can NOT be this difficult.
2 Weeks Ago #3
Rabbit
12,510 Expert Mod 8TB
Well, it's not C, but I threw this together in javascript of you want to take a look. It just outputs to the console so you'll have to open up your browser's console or the console that the site provides.

https://jsfiddle.net/thru41wj/

Expand|Select|Wrap|Line Numbers
  1. class PriorityQueue {
  2.   constructor() {
  3.     this.collection = [];
  4.   }
  5.  
  6.   enqueue(element, priority){
  7.     let added = false;
  8.  
  9.     for (let i = 0; i < this.collection.length; i++){
  10.       if (priority < this.collection[i][1]) {
  11.         this.collection.splice(i, 0, [element, priority]);
  12.         added = true;
  13.         break;
  14.       }
  15.     }
  16.  
  17.     if (!added) {
  18.       this.collection.push([element, priority]);
  19.     }
  20.   }
  21.  
  22.   dequeue() {
  23.     return this.collection.shift();
  24.   }
  25.  
  26.   size() {
  27.     return this.collection.length;
  28.   }
  29. }
  30.  
  31.  
  32.  
  33. const grid = [
  34.   [1        , 1         , 5         , 2         , 1         , 1         , 1 ],
  35.   [Infinity , 2         , 1         , 2         , 5         , 1         , 1 ],
  36.   [Infinity , 9         , 1         , 2         , 5         , 1         , 1 ],
  37.   [Infinity , 1         , 5         , Infinity  , Infinity  , 1         , 1 ],
  38.   [Infinity , 1         , 5         , 2         , 1         , 1         , 1 ],
  39.   [Infinity , 1         , 5         , 2         , 1         , 1         , 1 ],
  40.   [Infinity , 1         , 5         , 2         , 1         , 1         , 1 ],
  41.   [Infinity , 1         , 5         , 2         , 1         , 1         , 9 ],
  42.   [Infinity , 1         , 5         , 2         , 1         , Infinity  , 9 ],
  43.   [Infinity , 1         , 5         , 2         , 1         , 1         , 1 ],
  44. ];
  45.  
  46. const gridHeight = grid.length;
  47. const gridWidth = grid[0].length;
  48. const startNode = calcNodeID(0, 0, gridWidth);
  49. const endNode = calcNodeID(6, 9, gridWidth);
  50.  
  51.  
  52. const { distance, previous } = dijkstra(grid, gridWidth, gridHeight, startNode, endNode);
  53. const shortestPath = getShortestPath(gridWidth, distance, previous, startNode, endNode);
  54.  
  55.  
  56. const drawnPath = [];
  57. const startCell = shortestPath.shift();
  58. const endCell = shortestPath.pop();
  59.  
  60. for (let i = 0; i < gridHeight; i++) {
  61.   drawnPath.push(new Array(gridWidth).fill('_'));
  62. }
  63.  
  64. drawnPath[startCell[1]][startCell[0]] = 'S';
  65. drawnPath[endCell[1]][endCell[0]] = 'E';
  66. shortestPath.forEach(cell => drawnPath[cell[1]][cell[0]] = 'X');
  67.  
  68. console.log('shortest distances array:', distance);
  69. console.log('previous node taken array:', previous);
  70. console.log('\n' + drawnPath.map(row => row.join(' | ')).join('\n') + '\n');
  71.  
  72.  
  73.  
  74. function calcNodeID(x, y, gridWidth) {
  75.   return y * gridWidth + x;
  76. }
  77.  
  78.  
  79. function calcNodeXY(nodeID, gridWidth) {
  80.   const x = nodeID % gridWidth;
  81.   const y = Math.floor(nodeID / gridWidth);
  82.   return [x, y];
  83. }
  84.  
  85.  
  86. function dijkstra(grid, gridWidth, gridHeight, start, end = null) {
  87.     // list of transforms to apply to find orthogonal edges
  88.   const transforms = [[-1, 0], [0, -1], [1, 0], [0, 1]];
  89.   // additional diagonal edges if wanted
  90.   //, [-1, -1], [-1, 1], [1, -1], [1, 1]];
  91.  
  92.   const pq = new PriorityQueue();
  93.   const numNodes = gridWidth * gridHeight;
  94.   const visited = new Array(numNodes).fill(false);
  95.   const previous = new Array(numNodes).fill(null);
  96.   const distance = new Array(numNodes).fill(Infinity);
  97.  
  98.   distance[start] = 0;
  99.   pq.enqueue(start, 0);
  100.  
  101.   while (pq.size() > 0) {
  102.     const [current, minValue] = pq.dequeue();
  103.     const nodeXY = calcNodeXY(current, gridWidth);
  104.     visited[current] = true;
  105.  
  106.     if (distance[current] < minValue) continue;
  107.  
  108.     // normally a loop of all edges, adjusted for grid
  109.     for (const transform of transforms) {
  110.       const nodeToVisitX = nodeXY[0] + transform[0];
  111.       const nodeToVisitY = nodeXY[1] + transform[1];
  112.       const nodeToVisit = calcNodeID(nodeToVisitX, nodeToVisitY, gridWidth);
  113.  
  114.       if (nodeToVisitX < 0 || nodeToVisitY < 0 || nodeToVisitX >= gridWidth || nodeToVisitY >= gridHeight) continue;
  115.       if (visited[nodeToVisit]) continue;
  116.  
  117.       newDistance = distance[current] + grid[nodeToVisitY][nodeToVisitX];
  118.       if (newDistance < distance[nodeToVisit]) {
  119.         previous[nodeToVisit] = current;
  120.         distance[nodeToVisit] = newDistance;
  121.         pq.enqueue(nodeToVisit, newDistance);
  122.       }
  123.     }
  124.  
  125.     if (current == end) break;
  126.   }
  127.  
  128.  
  129.   return { distance, previous };
  130. }
  131.  
  132.  
  133. function getShortestPath(gridWidth, distance, previous, start, end) {
  134.   const path = [];
  135.  
  136.   if (distance[end] == Infinity) return path;
  137.  
  138.   for (let current = end; current != null; current = previous[current]) {
  139.     path.push(calcNodeXY(current, gridWidth));
  140.   }
  141.  
  142.   return path.reverse();
  143. }
2 Weeks Ago #4
SwissProgrammer
206 128KB
I apologize.

I should have fought with this on my own.

Please someone remove this entire thread.
2 Weeks Ago #5
Rabbit
12,510 Expert Mod 8TB
Rather than deleting it, it would probably be more useful for future readers to know what breakthrough helped you out
2 Weeks Ago #6
SwissProgrammer
206 128KB
Thank you Rabbit.

I did not get it to work.

Thank you for adding your code example. That was nice.

Thank you Rabbit.
2 Weeks Ago #7
Rabbit
12,510 Expert Mod 8TB
Well if the question is unresolved, then even more reason to not delete it
2 Weeks Ago #8
SwissProgrammer
206 128KB
That was me giving up again. And then you helping me to keep trying.

I like this site so much. Thank you.
1 Week Ago #9

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

6 posts views Thread by Lau | last post: by
6 posts views Thread by ThanhVu Nguyen | last post: by
5 posts views Thread by leezard | last post: by
4 posts views Thread by Shuch | last post: by
2 posts views Thread by Bytter | last post: by
5 posts views Thread by aleya | last post: by
3 posts views Thread by didacticone | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.