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.
8 4682
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.
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.
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();
-
}
I apologize.
I should have fought with this on my own.
Please someone remove this entire thread.
Rather than deleting it, it would probably be more useful for future readers to know what breakthrough helped you out
Thank you Rabbit.
I did not get it to work.
Thank you for adding your code example. That was nice.
Thank you Rabbit.
Well if the question is unresolved, then even more reason to not delete it
That was me giving up again. And then you helping me to keep trying.
I like this site so much. Thank you.
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
|
20 posts
views
Thread by Webdad |
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
| | | | | | | | | | | | |