Path Planning #2 Wave Propagation, Potential Fields & Modern(ish) C++
Vložit
- čas přidán 24. 11. 2018
- In this video I look at an alternative to A* algorithm for finding shortest paths. Information can be propagated relating to distance along a wavefront, that ripples across an isomorphic data structure.
Source: github.com/OneLoneCoder/Javid...
Patreon: / javidx9
/ discord
Blog: www.onelonecoder.com
Twitter: @javidx9
Twitch: javidx9 - Věda a technologie
Hello, two quick things! 1) I'm fully aware that this implementation is NOT OPTIMISED. There are ways to make this faster, but I wanted to show and use some modern C++ ideas. 2) My apologies for the voice changing. Half was filmed with my morning voice, and half with my evening voice which is unusual for me, but some IRL stuff got in the way!
hey isnt this same as (or similar to) plain old Breadth first search?
Hi Shubham, yes it is!
@@javidx9 lol, as i thought
I have a question about lambda definition in the scope of OnUserUpdate function.
is it created every time whenever the function is called?
@@slvrization technically yes, but compiler may optimize this.
I love your videos bc the kind of linear logical math thinking you need for programming doesn’t come naturally to me, but your explanations help me see things from another perspective
That's really encouraging to hear Cameron, thanks for your comment!
Amazing. So cool to see the dynamic pathfinding, as you make obstacles.
Thanks Stig!
You are a goldmine of knowledge and an amazing teacher!
Hey Javid, first of all your explanation is very good both verbally as well as visually also and it would be very helpful if you can explain about local minima trap in potential fields and how we can avoid it
yay, new video
Very good work and well explained topic, mate! Keep it up!
Hey thanks Pard!
javidx9 You're welcome, mate!
This may be very useful to my friends making similar projects
Good stuff Meeharbi! Pass it on!
I done this exact algorithm for my Deluxe Pacman game years ago. Except, it didn't have a name that I knew of, it's just something I came up with. I didn't mark duplicate nodes discovered already though. Instead, I would have a flag which indicated that node had already been discovered. Either a separate flag for each node, or just set the node value to something like -2, which would indicate it was a node you already discovered an added to your list. This way you have no need to search for duplicates.
One huge benefit of this method, is in my game, I only had to update it when pacman (the target) moved to a new node. And even then, it was the ghosts that use this to path to him, they only needed to update it when they reached a junction where they needed to choose from several paths available. If the target hadn't moved to a new node, they could use the existing path map. The beauty of this is, no matter how many ghosts I have (four) that need this path, they can ALL use the same path map because the numbers all have to do with the target and the distance from the target in each node, so just pick ANY starting point after you calculated the distance for each node, and you can see that you can find the shortest path from any point to the target without recalculating.
Very handy, especially for games where the target doesn't move, but the source location can change or have multiple units using it (a group of infantry or tanks all headed towards a building to destroy from all over the map for example).
Edit: LOL, I guess I should have watched the whole video before I typed this. ;)
Hi Neil, as usual, thanks for an excellent contribution! I guess it would be quite interesting to use this technique to bias the ghosts, and still allow them to have unique personalities.
Great video.
Great video, even with twin voices :-) Learned a lot! Thank you.
Thanks John, I dont know why it varies so much throughout the day XD
@@javidx9 Let's investigate :-D
www.medicaldaily.com/raspy-voice-morning-heres-why-your-voice-changes-day-goes-318248
you are simply the best
Thanks man, maybe not the best but appreciated!
Nice video there
Cheers buddy!
another cool view
Thanks zybnek!
@@javidx9 i was played project hospital and i was wonder why actors using so much turns, and going throw rooms, where thay walk around things, instead of walk straight by coridor.
Now i know coders use wave path finding in two steps, in first step they calculate with walls and doors, and in second at level of room, however actor looks for path throw room after entered in, and result is: longer way and many turns.
Thank you, very interesting and helpful video. I have a question, why didn't we just use to automatically remove duplicates and sort the values. Or if we didn't want to sort we could use which removes duplicates and works in constant time O(1)
Sets are an excellent way to implement this, though I would need to explain how the properties of the sets work, and this video was long enough already, so I stuck with technology Ive shown in previous videos in this instance. To be fair, the use of std at all is probably overkill, and with the addition of a few more flags in the cells, you may remove the need for it entirely.
@@javidx9 Ok. Thank you for reply. I'm fan of your video series!
Good
Hello, I have a question about your older type videos (console games). Let's say I have a simple player which is represented by 'X'. It is possible to draw and move it using floating position? (in console). Also your engine helped me a lot with constructing console etc. (I'm not using it beacuse I'm creating school project), windows.h has awful variables and functions names, even TRUE is capitalized, lol. Love your videos too (hate your naming habit e.g nPosition tho). Thanks for response.
Hi Eminiox, thanks! The position can be floating int, but it will be truncated to an integer to suit the display
@@javidx9 Thanks, but i have another problem. I want to display '▼' (0x25BC) but when I'm writing output it displays some weird symbol. I've tried to SetConsoleOutputCP(CP_UTF8); but it displays box with '?' inside then. My declaration is CHAR_INFO character; character.char.UnicodeChar = 0x025BC (Yes i turned on unicode in vs project settings, this symbol is also supported by consolas font).
@javidx9 are u able to do a* program for special order on different languages ?
Yee!
Hello Javidx9! Fantastic videos on your channel, always pleasant to watch.
I have one question though, what was the main reason why you've chosen C++ over C back in the day?
And what do you think about C pros over C++ in terms of GameDev? (if there are any :) )
Hi silverthorne and thanks! My opinion here is going to be controversial but hey at least I'm honest :D I don't believe there is really any justification to choose C over C++ these days. Even beginners should just go straight into C++. OOP brings more advantages than disadvantages, and you can elect to use it or not. I actually started with C as C++ wasnt really a thing yet. I also really liked Pascal too! If you write C like code in C++, the compiler will create the same result regardless.
@@javidx9 I agree about OOP, cause I am personally Scala programmer in the day time :)
But couple of weeks ago I've (all of a sudden!) revisisted C language after 10 years of giving up and just for fun started to write some small stuff using SDL2 library, like simple rain with splash particles, 3d cubes with all the projections and rotations math, some algorithms visualisations (using pthreads for recursive ones! omg) and so on, publishing it on my github.
Oh my, I'll remember how happy I was when I managed to understand how to work with arrays of pointers to structures at the first time! All the memory management stuff, it's just new (well, not new, but very well forgotten) and very fascinating.
By now I'm considering to write some small game and I'm a bit confused about language choice.. Well, the question is more like should I stick with C, cause from one side I like it's simplicity and straitforwardness, on the other - features like polymorphism could be just mimicked in not a very convenient way, there is no standard thread library (well, pthreads may be somewhat standard for POSIX), and labmdas in C++ are clearly of a very good use for me. However, I'm not a big fan of a newer C++ features like smart pointers and other magical stuff.
20:41: WHOO HOO! Proper use of curly braces!
lol, I agree entirely Peter!
great video
what is the best book in data structure?plz
Thanks Shady - I'm afraid ive not read any computing books in a long time, so I dont know whats currently good, sorry!
@@javidx9 anyway realy thanx
Good luck
It's just a simple BFS in algorithm aspect.
Correct!
After watching almost every video in this channel I realized you always use two variable two represent a point in 2D, why not use a struct with X and Y? Any particular reason or that's just how you've always done?
It doesn't matter, it's just his preference
@javidx9 Sets can help you out agains the duplications.
Hi Surf, yeah, but ive not used sets in any previous videos yet. I dont want to use things without explaining them first. But sets are a good solution, maybe a little overkill, i think the most optimal is to adjust the array to contain "discovered" information.
Can you explain implementation of the draw(...) Or drawline(...) Function? Ive seen you using it in making od 3d engine and other videos. How does it work? Btv i have seen olcconsolegameengine explanation and it didnt satisfy me...
I might do a specific video about the drawing routines in the near future. I may be telling you something you already know, so my apologies, but i break the screen up into a 2D array of "characters" or "pixels" - the draw() function just sets a specific pixel to a value that indicates its colour. The engines then take this array and translate it to something that can be viewed on screen, for olcConsoleGameEngine, this is outputting a text buffer to the command prompt, and for olcPixelGameEngine, the array is drawn as a texture onto a quadrilateral polygon and then rendered to the screen via the GPU. The drawline() function is a bit more complex, perhaps too complex for a youtube comment, but it implements Bresenhams line drawing algorithm - a routine that only uses integer additions/subtractions to select pixels to be drawn, based upon the gradient of the line.
@@javidx9 Yes please hah, i would realy like to see that drawing routines. All the math behind it does not scare me, just like for 3d engine, it was really well explained and thank you for that. But if i can edit my orginal question from lets say diffrent perspective, i would like to ask , would it be possible to write a c/c++ code to implement same draw function without using third party libraries like opengl, vulkan... Or STL if there is any. So kinda example what im asking is: lets have function that returns greter of two passed arguments. And body of that function will contain something like :
{ return a>b? a:b; }. So what would be body of that draw function, if we dont use any graphics libraries, just pure c++? Is it actualy possible?
Its absolutely possible, simply have a look at the olcPixelGameEngine.h file, the routines are fully exposed and assume no third party libraries or graphics dependencies.
Okay... Tho i still feel im kinda missing some instructions, but i dont want to be too boring and just ask questions... I guess il figure it out eventualy... Anyway thanks for great content.
@@nikolabozin1187 he actually uses openGl, you can check the source on github
If one builds on this, it could potentially make a basic echo simulator
Why can't you mark a newly discovered node with its distance right away? That way, if in the same propagation round, another node finds it it will immediately know it was already found. Isn't it guaranteed that each round always finds new nodes at the same distance away from the target? The whole duplicate removal seems redundant... But maybe I'm just tired. Wonderful video as always!!
Ah, javidx9, saw your comment now about 'em modern c++ shenanigans...
Thanks Mikael! Oh yes, there are many ways to optimise this technique, another could be to use std::set, but most definitely using additional data in the cells is an option too.
do you have a Dijkstra video?
Go to 30:16 in his A* video
Can we change the size in the DrawString function?
In PGE yes, it can be scaled by supplying an integer scaling coefficient as part of the call, and DrawStringDecal supports arbitrary scaling.
@@javidx9 a-ok I understand now, another engine
This algo is most likely used in fire emblem for character and cursor movement. Very cool.
I have a question: do we have to download anything such as a Flowfield Pathfinder. I checked and it's on sale. If I can do things like this video I happily buy it but I need to know exactly what I'm download. Please let me know.
You do not need to buy anything to do what is shown in this video.
do you have a video that explain how to implements A star for multiple agents trying to reach multiple destinations
Why you doesnt use for(&a : path) ? 39:05
Hi IFon, I need to declare the variable a before I can use it. The auto keyword does this for me.
Why use a list and not a vector?
If only I could figure out how to make this work in a 2d platformer
i found this kata to be quite intresting. its more or less the same principal as usual path finding but with a nice twitst and some nostalgia for the old nes-games www.codewars.com/kata/ascii-games-warning-ice
also thanks for the video @javidx9 love to watch these before work.
Hi Mojodojo, pleased to hear you are still enjoying the videos! I love old NES games :D
This looks like an airplane schema xd
What is the framework that you usually use when creating the maps and other GUIs?
Seems like Dijkstra
Same thought
It is a bit like Dijkstra, but assumes all paths are of length 1.
@@javidx9 But it doesn't gain any relevant improvement that way. Except, you could evaluate the whole wavefront in parallel, as you don't need to sort, you can just expect all of them to be the next minimum.
djikstra
how does this wave propagation pathing compare with flow field pathfinding?
this could also be sweep, multipass, filled, mine sweeper style, single 2d or 3d array needed, single toggle z-buffer for direct visibility 2.5d or 3d
so much code for so little, well, at least you are there to do the nasty uninteresting work for me
do you get what is slavery and what is not
autogenerated algorithm to implementation, algorithmic generalized description language, generalized Java
btw, single dimension sort collisions, quick boundary match
for 2d and 3d systems, if center of collision form is close enough to touch another collision form center, might have also the size of the collision form, or split a large collision form to many same size collision forms, like boxes
How can I find the longest path not using an algorithm with NP complexity?
take my D value
d value
You are not funny