The Pathfinding for OVUS NOVA! (Walls) - Part 1

hey this job's making video games with you and today I want to implement walls or pathfinding into my game over snow much more difficult I don't know if you can finish it today but first of all let's explain why this is so complicated and how I plan to do this you know you have to worry a little bit about performance and all that sort of stuff so let's have a short look see at the problem so I'm probably gonna do grid based pathfinding now those red things are enemies those blue things are eggs you see the point we don't know if the closest one is also the one that is really the closest one when we consider all the walls if we use standard pathfinding we would have to do pathfinding from the sky to every single egg in the entire room just to figure out which eggs actually the closest model we don't want to do that sounds like it would cost a lot of performance so what I want to use a flat fill pathfinding and what that allows us to do is use pretty much as many enemies as

we want and how it works is relatively simple pretty much fill the entire screen with paths so we start directly next to the X and say okay this is the shortest path to the egg this is the shortest path to the egg and once you've done that we can just start with the next fields tada and suddenly we know in a two-tire radius what the closest way to the egg is and then if you just keep doing this if you do this again and again and again then Sammy all those red creatures need to do is just follow the paths because at some point we just have the entire map with those blue paths that basically just show the direction to the closest deck and the hallway enemies need to do is follow those directions that is pretty good for the performer you have a lot of enemies the bad thing about this is that costs a lot of performance to generate it so we'll have to see if that is a trade-off worth taking at the moment I think yeah probably so I'm gonna try it and then

also want problem with this is that the paths are not really a direct connection but they have some straight lines and some plain diagonal line so maybe enemies don't always take the straight route take a little bit of a janky path some edgy directions but we'll see we'll see so what I'll do is I'll create a new can make a project because I don't want to just program that in the host Nova project I just want to try out if this works how it performs and then if it works we can bring it into the office Nova project so let's have a new little can make a project and try it there a few Bob ed later is always the best of three starts with writing a black report to you you games because they can fix a few Bob ed later okay do you know it's better if you write a back report and then figure out it was your own mistake whew Bob okay here you can see how I build systems like this from ground up and the the important part is that you

really take it step by step don't try to create everything at once really just think about what's the first important step I need to take and then do that Green are the X red are the enemies so a little prototype of how this could look later on how level like this could look and now everything I did is I transferred to this data to an array buffer to a buffer that starts this data and that I can use to perform my calculations because I cannot do the calculations purely with the objects right here first thing I did is I transform recruited former and made sure that everything shows up at the correct position here you can see a little bit of how this is drawn as you can see I'm using buffers and I use a for loop to loop through that buffer and yeah that's the first step let's continue with the next step okay I got a little further now but visualizing this stuff is so important you can clearly see this is completely messed up that's not how it should look like at all basically what I want to show is the distance to the closest act firstly it's a very small radius secondly

the hell did all of the walls disappear we should see still do the walls in black also why does it only check the distance to the right so I'll try to find the box let's see this is way better but far from perfect as you can see the walls are still not there and those white lines here as opposed to show the direction towards the closest deck at the moment they are showing harue glyphs I have absolutely no idea no clue okay look guys now it looks relatively good the only thing that doesn't look good is the calculation time because it takes really long to calculate while calculating we have zero frames per second that's way too long but then it looks like this like a beautiful rainbow and basically the color tells you how far each field is away from the next egg and then the little line tells you in which direction you need to go to get to the next egg it's a little hard to see because there are no there are no arrows they're just lines that face in the correct direction the only problem is here in the edges

the path finding slips through and in order to fix that I would have to use up even more calculation time so for now let's just plug those holes with additional blocks and then hopefully we can find additional ways to speed this up because the performance at the moment is absolutely not acceptable ok so here's one speed-up you can do in game maker that works pretty much all the time and is not not all that difficult to set up just change the target platform from Virtual Machine to you your compiler and all you need to do for that is install Visual Studio and link to the Visual Studio path and the preferences so this is virtual machine and what visual machine means is that all of the code is interpreted so it's not really compiled and as you can see here we have 0 frames per second if I press the Enter button in the virtual machines oh it's taking more than one frame to calculate the paths if I switch to virtual machine and try the same thing we already have two frames per second woohoo so that's let's say about four times as fast three times as fast four times as fast but of course it's still not enough it's far from perfect I

kind of want to make it work with a level of that size so obviously I could increase the performance dramatically by making the level a lot smaller that would help a lot okay now look at I added a lot more enemies to the room so we can check the performance a lot more and as you can see they automatically walk towards the closest X now and you can place new eggs unfortunately their performance is really bad you can see the FPS value up here 20 frames per second I improved it a little bit because the entire calculation is not done every single frame now the calculation is done over the course of 60 frames so basically we have split the calculation time it needs through 60 but then also if if we place an egg right here those creatures will take quite a while to realize that there's an egg here because it doesn't get updated that often but at least I can place X now in real time and we can also watch the pathfinding being done in return if we press the overlay button then I coat it

in and here you can basically see how the flat fill algorithm works it just starts from the X and basically fills the entire screen with the correct direction and with the correct distance the X just tell the creatures where to go basically if there are no more eggs or if the eggs are too far apart from each other it might happen that one egg isn't able to color the entire screen time for example if we look at the area up here it doesn't get painted because we don't go through enough iterations to paint all of that if I place an egg here now then obviously this area will be filled again and yeah this is virtual machine by the way if I switch to you your compiler it looks a lot better now as you can see the game runs a lot faster not with 60 unfortunately but with 50 frames per second so more than twice as fast which is also already a massive improvement but not nearly as good as I wanted to be so we will have

to do some further improvements on that pleasant egg here they take so long to realize that they can go there they feel really stupid this one as well because it just takes so long to update the pathfinding looks really interesting though when you see how how entire screen is filled yeah very nice very nice if you have any questions about how this system works ask them in the comments I tried to explain a little bit how all of this works in the video but I could imagine that it's a little hard to understand so if you have any questions feel free to leave them in the comments there will be a part two of this video where we continue developing the system and improving the performance and implementing this into the game and also if we only had that little checkers performance lithium issue we have a lot more checkers or I want to have a lot more checkers so I can make the walls a lot smaller and all that sort of stuff and therefore I want to continue improving the performance and spending a

little time on improving the performance is not a bad idea anyway so other than that thank you very much for watching have an amazing day make the world your playground and even the next one peace