Dijkstra

Calin said:
Im going to try not to use containers (Standard Template Library vector etc.)

Calin said:
I do all this because I find it easier going this route.

Dude…

Anyways, kudos for sticking with it - is your output nice?

SuperVGA said:
Anyways, kudos for sticking with it - is your output nice?

Its the first time Im doing things this way, I have yet to see if I can adapt to this new approach

There are several issues with your code - it would not even compile. If you expect others to look at it, you have to make it easy for them to read it. (It will help yourself later as well.)

arbm::S

That's terrible naming. What does arbm mean? What does S mean? Use meaningful names. It's more typing but still saves time later on deciphering your own obfuscated code.

Personally i often use this to have Getter and Setter at once, as i really hate to write them:

int& IntegerArray::Element(const int index)
{
	assert (index>=0 && index<Size()); // will notify only in debug mode; in release no check will happen at all.
	return container[index];

};

// or better, overwrite the [] operator instead:

int& IntegerArray::operator[](const int index)
{
	assert (index>=0 && index<Size()); // will notify only in debug mode; in release no check will happen at all.
	return container[index];

};

This way i can do both set and get, and it feels like a native array anyway:
iArray[5] = 7;
int seven = iArray[5];

You see C++ has some useful features making your life easier. (But the promises don't hold for long because const correctness often forces to write two versions again, but let's ignore this.)
Once you did this, you also understand how std::array works, and after that you will be fine using just that? Unlike std::vector it has no potential disadvantages.

Calin said:
Im going to keep several arrays of the same dimension, one array for each structure member. I do all this because I find it easier going this route.

A better reason to do such things is memory access optimization. If you mostly access most or all member variables of some struct while iterating it, it's usually best to have all data in such single struct. E.g. a vec3 or matrix4x4.

If you mostly access only a small set of data, e.g. struct Agent {vec2 pos; vec2 vel; char name[256];}; where you mostly read pos and vel but only rarely the name, it's probably a good idea to store names elsewhere like in their own array which can use the same index. It may help with caching and thus performance.
One route isn't really easier than the other, but it's hard to change such things later. I often spend time on making data structures or containers with some configurable SOA / AOS compromise, which is annoying. ('structure of arrays' vs. 'array or structs')
A general downside of SOA is: We can no longer use a single pointer - we use an index to address multiple arrays. The CPU thus needs the index AND the base addresses of all our arrays, so our data access needs more registers and to read base addresses first.
Personally i'm still bad at guessing which data layout is faster, so i have to do trial and error. But mostly i just keep using my initial design, which might be a bad one. Probably true for most people.

That's all just some unrelated background and has nothing to do with Dijkstra ofc. But graph traversal has bad access patterns, so it might have some noticeable effect on perf.

arbm stands for array of bools of medium size

arim - array of ints of medium size (medium because I also have other similar classes that have the array size set at 100 in the constructor)

I didnt include the headers for classes to keep the post short. Ill add them tomorrow

JoeJ said:
// or better, overwrite the [] operator instead:

I`m not comfortable enough with operator overloading yet.

Calin said:
I`m not comfortable enough with operator overloading yet.

You are comfortable after you start to use the new feature, not before it. ; )
It's really just a different syntax, otherwise there is nothing new to it.

Calin said:
medium because I also have other similar classes that have the array size set at 100 in the constructor

There is a language feature for this too, templates:

/*class Name32
	{
		static constexpr int LEN = 32;

		std::array<char,32> name;
	public:
		Name32()
		{
			name = {};
		}
		void Set(const char* string)
		{
			strncpy(name.data(), string, LEN);
			name[LEN-1] = 0;
		}
		void Set(const std::string &string)
		{
			Set(string.c_str());
		}
		void operator = (const char *string)
		{
			Set(string);
		}
		const char* Get() const {return name.data();}
	};*/

	template <size_t LEN>
	class NameN // todo: rename me to FixedSizeString
	{
		std::array<char,LEN> name;
	public:
		NameN()
		{
			name = {};
		}
		void Set(const char* string)
		{
			strncpy(name.data(), string, LEN);
			name[LEN-1] = 0;
		}
		void Set(const std::string &string)
		{
			Set(string.c_str());
		}
		void operator = (const char *string)
		{
			Set(string);
		}
		const char* Get() const {return name.data();}
	};

In this example i have some fixed sized string, and initially i have hard coded it's size to 32.
Thus, like you i need to copy paste and edit the whole code if i also want names only 8 chars long.
So i have just rewritten this code only once with almost no changes, and now i can do this:

//Name32 myName; // old class
NameN<32> myName; // new templated class

NameN<8> shortInfo;

Ofc. size needs to be a compile time constant, but that's exactly what we want.

I am really slow with adopting such ‘modern’ language features. Lacking interest in programming languages and laziness, you know.
But now you know some example, and once you really get tired about duplicated code, you may consider it.

Thanks,

JoeJ said:
It's really just a different syntax, otherwise there is nothing new to it.

It`s a new corner for me (that I will soon pass hopefully)

Thanks for posting about templates too.

anyways… this is the updated code for my Dijkstra implementation. The map is 20x20. I still have to insert the unwalkable and ‘last node’ arrays into the code.

Here's a Python implementation: https://towardsdatascience.com/solving-mazes-with-python-f7a412f2493f​

This is particularly cute because they ran it on a .png image of a maze, not some abstract representation. Note how it takes angled shortcuts.

(I have had the absolutely miserable experience of writing a maze solver in LInden Scripting Language. This is like pounding a screw. The language is totally wrong for the job, and the program, code, data, and stack, have to fit in 64K bytes. Works fine; I have NPCs in Second Life using it. But I never want to do that again.)

Nagle said:
Here's a Python implementation: https://towardsdatascience.com/solving-mazes-with-python-f7a412f2493f​ This is particularly cute because they ran it on a .png image of a maze, not some abstract representation. Note how it takes angled shortcuts.

Thanks for sharing Nagle.

[Edit]

Could A* be regarded as a Dijkstra algorithm that uses as node that has the shortest distance from the start all the adiacent/neighboring nodes of the start node?

[Edit#2]

This is the final version. Note: this is the state of the code before making any attempts at debugging.

almost done, the only thing left to do is to extract the path from the LastNode array.

Ive got the code debugged and working. heres the final result:

the source bug free. I have a memory leak somewhere in my project that makes passing int variables to the function impossible (I get trash values in them) so I made a class (ints) to store the variables I want to pass to the function.