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 5207
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.
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Lau |
last post by:
How do I easily calculate the shortest path between two geographical spots on
a map?
The map is divided into zones. So I guess it is possible to use Dijkstra’s
Shortest Path algorithm, but it...
|
by: ThanhVu Nguyen |
last post by:
Hi all,
I need recommendation for a very fast shortest path algorithm. The
edges are all directed, positive weights. Dijkstra shortest path will
solve it just fine but the if the graph is not...
|
by: Webdad |
last post by:
Hi!
I running my first year as industrial engineer (informatics)
We have an assignment to do :
.... create a playfield (matrix). Some places in that field are
blocked, so you can't pass them....
|
by: leezard |
last post by:
I am developing a program using VB.NET that will accept a start and end
point, the system then will generate the shortest path to reach the end
point. Anyone here have idea on doing this or some...
|
by: Shuch |
last post by:
Hi all,
I am in shortage of time...and i want to know if someone has a code
written in c++ or c for finding the shortest path using stack or
queue??????my specifications r as follow:
Input...
|
by: Bytter |
last post by:
Hi everyone,
I need to implement a very quick (performance-wise) Dijkstra shortest
path in python, and found that libboost already has such thing. Problem
is: I cannot find the installation...
|
by: aleya |
last post by:
I am developing a program using VB.NET that will accept a start and end
location (2 list boxes), the system then will generate the shortest path to reach the end point.
for your information i got a...
|
by: Nguyen2010 |
last post by:
Hello All,
I very need the code of the second shortest path or k-shortest paths that paths are separate(only same as source and destination) and find them almost parallel(not find the shortest...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |