🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Pathfinding, need feedback

Started by
109 comments, last by Calin 4 years, 1 month ago

Calin said:
I`m happy with my algorithm.

Although it does not work? WTF?

Advertisement

it works

My project`s facebook page is “DreamLand Page”

Congrats! : )

But the path is not a shortest one. (Make more tests to ensure it is always acceptable.)

This probably is only because you allow diagonal movement, which causes longer segments. So cost of straight move is 1 but diagonal move is 1.41 (sqrt(2).
You might need to add data to track this path length to the source from any node (was not necessary for my example which only moves straight).

Notice diagonal movement can allow to sneak through walls that look like this:

\XXX 
X\  X
X   X
 XXX

Needs more checks if you don't want that.

Cost management also allows cool options like having higher cost to walk over a swamp or through water, so entities can search paths to avoid this.

@calin , I see dijkstra path finding algorithm is too simple for you.

May I offer you something really advanced? You can use the Global Illumination data gathered for free by the advanced AI of NVidia RTX GPUs.

This is how it works -

You need to get the most to the left ray that diffusely reflects the destination. And then take the most to the right ray that brings you light-info about the destination.

Then, the point where two of the four rays intersect, is your path.
Easy peasy!
You could further scan the farthest each from other two points of these rays that can see each other(orange lines). Now you have the shortest path possible(yellow).

The advanced hardware of NVidia RTX Quadro GPUs do all that for you for free. You only need to take the info out of the GPU and use it.
Bats hunt that way and Robocop use it to shoot the enemies.

thanks JoeJ. I`m calling it mission accomplished.

the second tile that off is a precision problem I`m storing weights as ints.

JoeJ said:
But the path is not a shortest one

when I run the algorithm backwards it does pick the shorter path.

@nikito how inspirational , perfect good night story.

My project`s facebook page is “DreamLand Page”

To keep the post count down I`m editing my posts instead of making new ones

My project`s facebook page is “DreamLand Page”

Calin said:
@nikito how inspirational , perfect good night story.

Calin said:
To keep the post count down I`m editing my posts instead of making new ones

Good. Because your one line of text posts take so much space here. :P

JoeJ said:
Because your one line of text posts take so much space here

There are people with whom I talk more and people that I talk less with. It`s not wise to get into competition with (spiritually) agile people

My project`s facebook page is “DreamLand Page”

Calin said:
There are people with whom I talk more and people that I talk less with. It`s not wise to get into competition with (spiritually) agile people

I see. Reminds me on some old and wise chineese leader who calms his brave young warriors to not start a fight and have patience instead.

But by avoiding competition or argument you also avoid communication all together. This is not always wise either.

This topic is closed to new replies.

Advertisement