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

[SwissProgrammer]

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.

[Rabbit]

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.

[SwissProgrammer]

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.

[Rabbit]

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/

class PriorityQueue {
  constructor() {
    this.collection = [];
  }
  
  enqueue(element, priority){
    let added = false;
    
    for (let i = 0; i < this.collection.length; i++){
      if (priority < this.collection[i][1]) {
        this.collection.splice(i, 0, [element, priority]);
        added = true;
        break;
      }
    }
    
    if (!added) {
      this.collection.push([element, priority]);
    }
  }
  
  dequeue() {
    return this.collection.shift();
  }
  
  size() {
    return this.collection.length;
  }
}



const grid = [
  [1        , 1         , 5         , 2         , 1         , 1         , 1 ],
  [Infinity , 2         , 1         , 2         , 5         , 1         , 1 ],
  [Infinity , 9         , 1         , 2         , 5         , 1         , 1 ],
  [Infinity , 1         , 5         , Infinity  , Infinity  , 1         , 1 ],
  [Infinity , 1         , 5         , 2         , 1         , 1         , 1 ],
  [Infinity , 1         , 5         , 2         , 1         , 1         , 1 ],
  [Infinity , 1         , 5         , 2         , 1         , 1         , 1 ],
  [Infinity , 1         , 5         , 2         , 1         , 1         , 9 ],
  [Infinity , 1         , 5         , 2         , 1         , Infinity  , 9 ],
  [Infinity , 1         , 5         , 2         , 1         , 1         , 1 ],
];

const gridHeight = grid.length;
const gridWidth = grid[0].length;
const startNode = calcNodeID(0, 0, gridWidth);
const endNode = calcNodeID(6, 9, gridWidth);


const { distance, previous } = dijkstra(grid, gridWidth, gridHeight, startNode, endNode);
const shortestPath = getShortestPath(gridWidth, distance, previous, startNode, endNode);


const drawnPath = [];
const startCell = shortestPath.shift();
const endCell = shortestPath.pop();

for (let i = 0; i < gridHeight; i++) {
  drawnPath.push(new Array(gridWidth).fill('_'));
}

drawnPath[startCell[1]][startCell[0]] = 'S';
drawnPath[endCell[1]][endCell[0]] = 'E';
shortestPath.forEach(cell => drawnPath[cell[1]][cell[0]] = 'X');

console.log('shortest distances array:', distance);
console.log('previous node taken array:', previous);
console.log('\n' + drawnPath.map(row => row.join(' | ')).join('\n') + '\n');



function calcNodeID(x, y, gridWidth) {
  return y * gridWidth + x;
}


function calcNodeXY(nodeID, gridWidth) {
  const x = nodeID % gridWidth;
  const y = Math.floor(nodeID / gridWidth);
  return [x, y];
}


function dijkstra(grid, gridWidth, gridHeight, start, end = null) {
	// list of transforms to apply to find orthogonal edges
  const transforms = [[-1, 0], [0, -1], [1, 0], [0, 1]];
  // additional diagonal edges if wanted
  //, [-1, -1], [-1, 1], [1, -1], [1, 1]];

  const pq = new PriorityQueue();
  const numNodes = gridWidth * gridHeight;
  const visited = new Array(numNodes).fill(false);
  const previous = new Array(numNodes).fill(null);
  const distance = new Array(numNodes).fill(Infinity);
  
  distance[start] = 0;
  pq.enqueue(start, 0);
  
  while (pq.size() > 0) {
    const [current, minValue] = pq.dequeue();
    const nodeXY = calcNodeXY(current, gridWidth);
    visited[current] = true;
    
    if (distance[current] < minValue) continue;
    
    // normally a loop of all edges, adjusted for grid
    for (const transform of transforms) {
      const nodeToVisitX = nodeXY[0] + transform[0];
      const nodeToVisitY = nodeXY[1] + transform[1];
      const nodeToVisit = calcNodeID(nodeToVisitX, nodeToVisitY, gridWidth);
      
      if (nodeToVisitX < 0 || nodeToVisitY < 0 || nodeToVisitX >= gridWidth || nodeToVisitY >= gridHeight) continue;
      if (visited[nodeToVisit]) continue;
      
      newDistance = distance[current] + grid[nodeToVisitY][nodeToVisitX];
      if (newDistance < distance[nodeToVisit]) {
        previous[nodeToVisit] = current;
        distance[nodeToVisit] = newDistance;
        pq.enqueue(nodeToVisit, newDistance);
      }
    }
    
    if (current == end) break;
  }
  
  
  return { distance, previous };
}


function getShortestPath(gridWidth, distance, previous, start, end) {
  const path = [];
  
  if (distance[end] == Infinity) return path;
  
  for (let current = end; current != null; current = previous[current]) {
    path.push(calcNodeXY(current, gridWidth));
  }
  
  return path.reverse();
}

[SwissProgrammer]

I apologize.

I should have fought with this on my own.

Please someone remove this entire thread.

[Rabbit]

Rather than deleting it, it would probably be more useful for future readers to know what breakthrough helped you out

[SwissProgrammer]

Thank you Rabbit.

I did not get it to work.

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

Thank you Rabbit.

[Rabbit]

Well if the question is unresolved, then even more reason to not delete it

[SwissProgrammer]

That was me giving up again. And then you helping me to keep trying.

I like this site so much. Thank you.