Dijkstra's algorithm with C++ and GUI

[BobQuarter]

Dijkstra's algorithm. Help please. What steps do I use to make this work after reading the algorithm?

Just C++ please. No Visual C++. Thank you.

[againtry]

Are you sure a GUI interface wouldn’t help?

[BobQuarter]

GUI. Yes.

Please. That is what I am using.

I have studied the algorithm. I think that I understand it. I am asking for help in applying it to a tiny game map. The map is a bitmapped background in a WINAPI WinMain program. I can blt to the map. I am using a GUI. I am already there. The following is what I am asking for help with.


I can load a bitmap and see squares on it.
I can set a small image (game image of something) on a square at x and y position.
I can move the small image to a different x and y location.
But, how do I apply Dijkstra's algorithm to choose a shortest past as is described in the following?

/*
If I have a 5 square by 5 square game map like this

A square on the bitmap could be represented as


   0,0  |
   0    |
   ------

The entire map could be represented as


0,0  |1,0  |2,0  |3,0  |4,0  |
0    |x    |x    |x    |x    |
------------------------------
0,1  |1,1  |2,1  |3,1  |4,1  |
0    |x    |x    |x    |x    |
------------------------------
0,2  |1,2  |2,2  |3,2  |4,2  |
0    |x    |x    |x    |x    |
------------------------------
0,3  |1,3  |2,3  |3,3  |4,3  |
0    |x    |x    |x    |x    |
------------------------------
0,0  |1,4  |2,4  |3,4  |4,4  |
0    |0    |0    |x    |x    |
------------------------------

With 2,4 being column 2, row 4

With 0 or x:
0 = passable,
x = resistance to passable (some number above 5).

Then a shortest path from 0,0 to 3,4 could be 
0,0 
0,1
0,2
0,3
1,4
2,4
3,4

*/

I have been studying this. Help, please.

For someone that knows how, this should be very simple. I am still learning C++. I think that if I see some code that does this then I can study the commands and the structure used and apply this logic to a larger map.

Please give me an example that I can learn from.

Thank you.

No pictures in this question because I do not know how to add a picture to these posts.

Thank you.

[againtry]

It is not clear to me what your problem is but I am prepared to make a guess. Where you are mapping the results of applying the algorithm, one method is to adapt what is shown here:
http://www.cplusplus.com/forum/general/275331/#msg1188236

The operative model is described there with the words

The principle at work is the array is initialized, then the rectangle (results of algorithm) is inserted into the array, all hidden. Then finally the array is cout'ed ie drawn to the screen.

If you are using a GUI interface then you would probably use some form of text box to display the algorithm outcome in the associated grid-matrix format.

[BobQuarter]

againtry,

Thank you. I have now studied arrays. I am now using them.

But, an array of strings seems to be wasteful compared to a single string which can hold a lot by itself.



If I have a string with 4,000 different strings of maximum length 12 in an array such as

std::string SomeString [4000] [12];

Would the executable run faster with less memory if I use one string to hold all of that and then parse the one string for each sub string each time that I need to access that part of the string?


It would be nice if I could show you a picture of what I am testing.

Thank you.

[skcpp]

BobQuarter,

In "...If I have a string with 4,000 different strings of maximum length 12 in an array such as...":

Did you mean "...an array [and not string] of 4,000 different strings..."?

[againtry]

@BobQuarter

To draw your map requires displaying 25 x 25 = 625 characters by the look of it. In terms of memory and processing time on a reasonable PC the time to do that is negligible.

A 2D array (ie your map) can be handled as a single string of 625+ characters - to include '\n's, or as 25 strings of 25 length or whatever. I'd use a 2D array because access is simple and what most in using a grid pattern.

I have no idea what you are driving at with 4000 strings (of whatever length).

Also note that each cell is on a 5 x 5 grid with each grid cell having 25 sub positions - maybe that's what you mean? I'd still group on cells and sub-cells.

A cell is a good opportunity for a class/struct :)

[BobQuarter]

skcpp,

Thank you.

The 5 x 5 is just a tiny example that I had hoped someone would give me some code that would work for that. Then I intended to study their process and re-write it to handle a much (very much) larger map. I wanted the process in C++ via a GUI interface (not CLI) that worked with a bitmap. I do not want to have to reinvent this when other people probably have something close already worked out. I am still learning and I have been making hours and days of mistakes getting to tiny amounts of working code.

Maybe I did not understand what std::string SomeString [max items] [max length]; meant. I mean to be able to handle 4000 items like "123 First St.", etc.



Example of using 4,000 etc.:

Houston, Texas has an estimated 2,320,268+ population covering approximately 637.5 square miles.

If I consider Houston houses and hotels and an average of 100 people per location that is still 23,202 locations.

And New York city has about four times the people at 8,336,817 with half the square miles.

4,000 locations is not too much. I am guessing at a max length of each location description at 12 characters for testing.

Thus, my question of which is better for cpu speed and memory use: an array of strings or a (one or more) long strings. I can access or parse each, but which is faster and uses less memory?



againtry,

Thank you.

The map is a tiny example for me to learn this process from. I specifically do not want to do this in CLI.

I specifically do want to be able to do this with a large map, about 64 squares x 64 squares. In testing I am using squares of 128 pixels by 128 pixels. That is a bitmap of 8192 pixels by 8192 pixels. I can handle that easily. The big map is not a problem. I want to have a tiny example of, "Dijkstra's algorithm with C++ and GUI" that I can learn from and re-write for the larger map situation.

No Command Line Interface. No.

Graphical Interface only.

I did not know how to send a bitmap to this forum, thus I used text (for this forum's posting). I do not want that type of output. No. I was just trying to get past the unavailability of posting a bitmap.


"A cell is a good opportunity for a class/struct :)" I have been looking for a really good example of class/struct that I (at my beginner level) can understand.




Thank you both.

I expect that someone here has worked through similar and has a small example that I can study that does not output text, but that does output to a GUI (like a game map). Ok, a Game Map. How to do this in a GUI game. Shortest time path for a game that uses a bitmap and moves an icon from square to square. I can do the bit block transfers already. I am interested in the "Dijkstra's algorithm with C++ and GUI" to make that work.

Working example please.

No CLI. No text output. Graphical User Interface. Bitmaps.

"Dijkstra's algorithm with C++ and GUI"


I expect that someone here has a little example that they can post. Please.


Thank you.

[againtry]

@BobQuarter
One way:
Teach yourself 3 things:
1. How to create a form view
2. How to draw a simple rectangle on the form - line color, width and size/position all under your control.
3. How to place test in the screen at coordinate position you choose.

Another alternative is to create an array of textboxes and display them on the screen. This gives you even easier control. The text boxes can be created dynamically. They don't have to be set up manually. You can have 1000's of them, whatever ..

Qt is ideal, Visual Studio isn't too bad ...

[BobQuarter]

againtry,

I have a lot of respect for you, but

I can create a form view. I do not get why you are avoiding the algorithm.
I can draw a simple rectangle, etc. [Same as above.]
I can place text on the screen. [Same as above.]
I can triple buffer screen graphics with animations and animated text. [That is not my question. I already made those clear in my post.]


I already told you:
"The big map is not a problem. I want to have a tiny example of, "Dijkstra's algorithm with C++ and GUI" that I can learn from and re-write for the larger map situation."

I already told you:
"I can do the bit block transfers already. I am interested in the "Dijkstra's algorithm with C++ and GUI" to make that work."

Thank you againtry.

[againtry]

https://www.geeksforgeeks.org/c-program-for-dijkstras-shortest-path-algorithm-greedy-algo-7/

[againtry]

https://www.programiz.com/dsa/dijkstra-algorithm

[BobQuarter]

againtry,

Thank you.

I think that you are helping. I am not to the answer yet, but getting there.



Your links lead me to https://www.reviewmylife.co.uk/blog/2008/07/15/dijkstras-algorithm-code-in-c/ which lead me to https://www.reviewmylife.co.uk/data/2008/0907/dijkstras-source-code.zip which I have been adapting from that mess to C++ starting by removing the stdafx.h and adjusting from there.

I now have yet another CLI based working example. Which I did not want.

I do not want this code.

This is CLI based code and I do not want it.

But,
I am now attempting to get this to work with a GUI and to get rid of the CLI stuff.

Maybe just completely replace it with a mathematical analysis of the shortest path and save that to arrays and use those arrays for shortest path results.

In case someone wants to see that page converted from the bloat and anti-security of Visual Studio into some semblance of C and C++, here it is.

// From Dijkstras.cpp
// Adjusted to remove the Visual Studio bloat and bring closer to C++.

// Step one remove stdafx.h .
// Step two replace stdafx.h dependencies with better C++ code.
// Step three analyze program and fix or replace any or all of it.


//#include "stdafx.h" // Removed stdafx.h , the disgusting convoluted mess.
                      // Without stdafx.h code works closer to C and C++.

                      // Adjusted in other places also.
                      // At least I am getting faster at removing Visual Studio from code examples
                      //    and bringing that code closer to clean C and clean C++.

                      // The following seems to me to be a waste of processing. I think that I should 
                      //    be able to dynamically adjust the weights and dynamically reevaluate the paths. 

                      // The following code looks like bloat to impress other coders.

                      // I think that this should be broken down into simply math equations,
                      //    then input into arrays which have changeable entries.

                      // I will be considering this further.

                      // Suggestions are appreciated.


#include <iostream>
#include <vector>

using namespace std;

void DijkstrasTest();

int main(int argc, char* argv[])
{
	DijkstrasTest();
	return 0;
}


//////////////

class Node;
class Edge;

void Dijkstras();
vector<Node*>* AdjacentRemainingNodes(Node* node);
Node* ExtractSmallest(vector<Node*>& nodes);
int Distance(Node* node1, Node* node2);
bool Contains(vector<Node*>& nodes, Node* node);
void PrintShortestRouteTo(Node* destination);

vector<Node*> nodes;
vector<Edge*> edges;

class Node   // This looks like bloat to impress. I think that I should process this in a simple mathematical formula.
{
public:
	Node(char id)
		: id(id), previous(NULL), distanceFromStart(INT_MAX)
	{
		nodes.push_back(this);
	}
public:
	char id;
	Node* previous;
	int distanceFromStart;
};


class Edge   // This looks like more bloat to impress. I think that I should process this in a simple mathematical formula.
{
public:
	Edge(Node* node1, Node* node2, int distance)
		: node1(node1), node2(node2), distance(distance)
	{
		edges.push_back(this);
	}
	bool Connects(Node* node1, Node* node2)
	{
		return (
			(node1 == this->node1 &&
			node2 == this->node2) ||
			(node1 == this->node2 &&
			node2 == this->node1));
	}
public:
	Node* node1;
	Node* node2;
	int distance;
};

///////////////////
void DijkstrasTest()   // This looks like more bloat to impress. I think that I should process this in a simple mathematical formula.
{
	Node* a = new Node('a');
	Node* b = new Node('b');
	Node* c = new Node('c');
	Node* d = new Node('d');
	Node* e = new Node('e');
	Node* f = new Node('f');
	Node* g = new Node('g');

	Edge* e1 = new Edge(a, c, 1);
	Edge* e2 = new Edge(a, d, 2);
	Edge* e3 = new Edge(b, c, 2);
	Edge* e4 = new Edge(c, d, 1);
	Edge* e5 = new Edge(b, f, 3);
	Edge* e6 = new Edge(c, e, 3);
	Edge* e7 = new Edge(e, f, 2);
	Edge* e8 = new Edge(d, g, 1);
	Edge* e9 = new Edge(g, f, 1);

	a->distanceFromStart = 0; // set start node
	Dijkstras();
	PrintShortestRouteTo(f);

	// TODO: Node / Edge memory cleanup not included
}

///////////////////

void Dijkstras()   // This looks maybe useful.
{
	while (nodes.size() > 0)
	{
		Node* smallest = ExtractSmallest(nodes);
		vector<Node*>* adjacentNodes =
			AdjacentRemainingNodes(smallest);

		const int size = adjacentNodes->size();
		for (int i=0; i<size; ++i)
		{
			Node* adjacent = adjacentNodes->at(i);
			int distance = Distance(smallest, adjacent) +
				smallest->distanceFromStart;

			if (distance < adjacent->distanceFromStart)
			{
				adjacent->distanceFromStart = distance;
				adjacent->previous = smallest;
			}
		}
		delete adjacentNodes;
	}
}

// Find the node with the smallest distance,
// remove it, and return it.
Node* ExtractSmallest(vector<Node*>& nodes)   // This looks maybe useful.
{
	int size = nodes.size();
	if (size == 0) return NULL;
	int smallestPosition = 0;
	Node* smallest = nodes.at(0);
	for (int i=1; i<size; ++i)
	{
		Node* current = nodes.at(i);
		if (current->distanceFromStart <
			smallest->distanceFromStart)
		{
			smallest = current;
			smallestPosition = i;
		}
	}
	nodes.erase(nodes.begin() + smallestPosition);
	return smallest;
}

// Return all nodes adjacent to 'node' which are still
// in the 'nodes' collection.
vector<Node*>* AdjacentRemainingNodes(Node* node)   // This looks maybe useful.
{
	vector<Node*>* adjacentNodes = new vector<Node*>();
	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		Node* adjacent = NULL;
		if (edge->node1 == node)
		{
			adjacent = edge->node2;
		}
		else if (edge->node2 == node)
		{
			adjacent = edge->node1;
		}
		if (adjacent && Contains(nodes, adjacent))
		{
			adjacentNodes->push_back(adjacent);
		}
	}
	return adjacentNodes;
}

// Return distance between two connected nodes
int Distance(Node* node1, Node* node2)   // This looks maybe useful.
{
	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		if (edge->Connects(node1, node2))
		{
			return edge->distance;
		}
	}
	return -1; // should never happen
}

// Does the 'nodes' vector contain 'node'
bool Contains(vector<Node*>& nodes, Node* node)  // Too much of the bloat is still being used. This might be useful but after adjusting.
{
	const int size = nodes.size();
	for(int i=0; i<size; ++i)
	{
		if (node == nodes.at(i))
		{
			return true;
		}
	}
	return false;
}

///////////////////

void PrintShortestRouteTo(Node* destination)   // This looks wasteful. This should have already been handled in the math analysis and then prepared for back buffer blitting.
{
	Node* previous = destination;
	cout << "Distance from start: "
		<< destination->distanceFromStart << endl;
	while (previous)
	{
		cout << previous->id << " ";
		previous = previous->previous;
	}
	cout << endl;
}




// these two not needed   // OK. There was other stuff not needed so far.
vector<Edge*>* AdjacentEdges(vector<Edge*>& Edges, Node* node);
void RemoveEdge(vector<Edge*>& Edges, Edge* edge);

vector<Edge*>* AdjacentEdges(vector<Edge*>& edges, Node* node)
{
	vector<Edge*>* adjacentEdges = new vector<Edge*>();

	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		if (edge->node1 == node)
		{
			cout << "adjacent: " << edge->node2->id << endl;
			adjacentEdges->push_back(edge);
		}
		else if (edge->node2 == node)
		{
			cout << "adjacent: " << edge->node1->id << endl;
			adjacentEdges->push_back(edge);
		}
	}
	return adjacentEdges;
}

void RemoveEdge(vector<Edge*>& edges, Edge* edge)   // Delete it. Use something else.
{
	vector<Edge*>::iterator it;
	for (it=edges.begin(); it<edges.end(); ++it)
	{
		if (*it == edge)
		{
			edges.erase(it);
			return;
		}
	}
}

Thank you.