NikiTo said:
Because “prevVertex” could be misunderstand as “previousVertex”

I meant previous here, not preview.

NikiTo said:
(Shouldn't “int curVertex = grower.Next();” be “int curVertInd = grower.NextAndPush();” instead?. A method “next()” makes me think of a Timer. Maybe better “step()” or “grow()”.)

Well, naming things is hard. : )

NikiTo said:
Replace “for(;;)” with

for ( ; ; ) is faster than while (true). At least it was decades ago, people said.

JoeJ said:
Well, naming things is hard. : )

It is indeed. I name things bad usually and go that way. And when i am stuck with debugging, staring at the code for hours to find that sneaky one letter error, then i rename it all. But my project is not big, i can even use temp0, temp1, temp2 IF, ONLY IF i consume it few lines of code after the declaration and never again. This way, even a temp variable is known what it does. Because finding a good name takes time too, and i am in a hurry.

JoeJ said:
for ( ; ; ) is faster than while (true). At least it was decades ago, people said.

Compilers should always produce the fastest code. The job of a compiler is to produce always the fastest code, regardless you write it ++i or i++. Just use the easiest code to code and let the rest to the compiler. I am using a compiler, and i don't worry if the compiler can do its job. Because if the compiler can not understand that “for(;;)” and “while(true)” are the same thing, this is not my fault and i sleep fine at night.

If you use a compiler(like me now) you should focus on the algorithm and completely ignore the produced bytecode. This is the job of a compiler. Don't try to think for the compiler, and for the OS too. Let people who create these, to make their job. You focus on your own job - the algorithm.

Right now you don't need too much speed. But imagine you needed speed with that code. Before trying to compile two versions with for and while and compare the timings, you should first solve that “two nested while true loops” first. Maybe save at some place the current best walked path distance and when you want to visualize it, don't for(;;) it again, but just read from a list that was prepared as an extra during the scan.

Just an example. Maybe not the best. To explain my point of view of "sucking speed from the algorithm" vs "sucking speed from the compiler" priorities.

Maybe the last thing you do, just before publishing your finished game, could be looking at the bytecode and trying to improve it.

NikiTo said:
Maybe the last thing you do, just before publishing your finished game, could be looking at the bytecode and trying to improve it.

Sure, introduce errors into your Java app hours before you go gold, sounds like a great idea.

fleabay said:
Sure, introduce errors into your Java app hours before you go gold, sounds like a great idea.

https://en.wikipedia.org/wiki/Unit_testing

JoeJ said:
Show the path(s) to see if it's correct:

[edit] I finished the algorithm. I`m not posting the code update, the only things added are `no path` handling and final path retrieval from the trunk.

it`s still buggy, map size:

NikiTo said:
you should first solve that “two nested while true loops” first. Maybe save at some place the current best walked path distance and when you want to visualize it, don't for(;;) it again, but just read from a list that was prepared as an extra during the scan.

If we look at execution flow, there are no nested loops in my example code, notice the inner loop is started only after the goal has been found, and after extracting the path from the data it breaks out of the outer loop as well.
It would be better to break out of the path creation loop when the goal is found, and start the path extraction after that to make this clear (and help the compiler to figure this out).

NikiTo said:
Maybe the last thing you do, just before publishing your finished game, could be looking at the bytecode and trying to improve it.

This does not work for two reasons:

If we do not care about performance all the time, we would end up at rewriting everything after we are done. So spending too much time and introducing to many bugs.

And second, it becomes impossible to optimize because we can not find all the bottlenecks. We may find a small number of really bad ones, but after optimizing those few cases we no longer see any further bottlenecks. Every part of the program takes roughly the same 1% of processing time.
Looking at this it seems there is no more reason to optimize further because nothing will have any noticeable effect. So we would decide to leave it at this, although in reality the whole code may be slow.

That's why we better care for performance all the time. Even if we have other goals as well which may appear more important.

Calin said:
it`s still buggy here`s a scenario that doesn`t work

Looks like it visits disconnected islands… it's a total mess, man. I am not surprised it does not work - i was pretty sure it would not.

Listen: Dijkstra is the simplest possible algorithm to find shortest paths. You say you want a simple solution easy to maintain, and it does not have to be as fast as possible. This is exactly what my example code on page 3 is doing. (It is simple Dijkstra algorithm without using a queue to add path segments in optimal order to find the path faster).

So you have two options:

1. Continue to reinvent the wheel, which would bring you to the exact same algorithm!!!
(We would have and use this algorithm even if Mr. Dijkstra never existed - it's just coincidence the algo is named by him.)

2. Understand how my example works, or just use it. It is fine to use things even if we do not know exactly how they work. E.g., almost nobody understands quaternions, but everybody uses them. And it just works.
After some time, you may need to understand to improve. Usually this happens, and you learn those things even if you did not understand all the details in the first place.
If you want to understand it fully right now, simply ask on a certain detail you do not understand. Then you usually get good answers, if you describe what you have, what you want, and what does not work.

The difference between those 2 options is the amount of wasted time which could have been invested in a better way.

JoeJ said:
If we look at execution flow, there are no nested loops in my example code, notice the inner loop is started only after the goal has been found, and after extracting the path from the data it breaks out of the outer loop as well.

My bad.

JoeJ said:
This does not work for two reasons:

Generally, while one is coding, he constantly keeps in mind the good practices. This is enough optimization during coding. Peeking at the assembly in the midway of the development, looks like Premature Optimization to me.

You might think i am contradicting myself, because you know i counted the registers by hand in a shader.
But in my case i simply can not keep developing with a shader that takes 12 minutes to finish. So in order to unstuck my development, i need to optimize. Now, that my 12 min shader became 10secs only, i can develop further. I need to run the app hundreds of times daily. Impossible with a shader that takes 12 mins to complete. (and i am not counting the registers by hand no more. I grew up toward productivity a bit in that aspect.)

@nikito agree.

@calin

Explaining that dumb simple Dijkstra example in 1D, which we could also describe as BFS or floodfill algorithm with additionally storing the previous node to extract paths.

First, initialize our per cell data.
98888889
9 = obstcle, 8 is large number. Numbers mean how 'distant' the current node is. We visit smaller numbers first.

98808889
we set the distance at the start to zero. Then we check adjacent nodes and visit them if their distance is larger, increasing current distance by one. We continue until every node has been visited.

98101889
92101289
32101234
Now every node has been visited and we are done.

We now know the shortest path to the start from every node.
So to get the path from any point, just follow tha path of decreasing distance the most. ('local maxima search')
But because we may have equal distance values multiple times, we did store the links to previous nodes while processing to make it easier.

Extending this to higher dimensions is the same algorithm.

It is that simple, Calin.

JoeJ said:
simple Dijkstra example in 1D

It never crossed my mind you could pathfind in a string, but I`m happy with my algorithm.