Path Finding in UPBGE for Dani's Race
👁 109
https://mastodon.social/ : 👁 4
https://lemmy.dbzer0.com/ : 👁 1
https://blenderdumbass.org/ : 👁 2
https://blenderdumbass.org/search?text=%23UPBGE&tags=on : 👁 1
https://blenderdumbass.org/articles : 👁 1
https://mastodon.uno/ : 👁 1
https://www.google.com/ : 👁 1
![[avatar]](/pictures/favicon.png)
by Blender Dumbass
Aka: J.Y. Amihud. A Jewish by blood, multifaceted artist with experience in film-making, visual effects, programming, game development, music and more. A philosopher at heart. An activist for freedom and privacy. Anti-Paternalist. A user of Libre Software. Speaking at least 3 human languages. The writer and director of the 2023 film "Moria's Race" and the lead developer of it's game sequel "Dani's Race".
Information or opinions might not be up to date.
Here is a scene for you. You messed up a race. Your Paps is very very mad at you right now. He doesn't trust you to drive. Yet he wants to teach you to drive. So he takes you to a karting club. This is a scene I'm working on in Dani's Race right now. A scene in a video game I'm making which should not have cut scenes. Which means, for this scene to work, Paps needs to walk from his room to a car, wait for you, the player to sit with him into said car, and then drive you across a town to a completely different location. Seamlessly. ↩ Reply
![[embedded image]](/pictures/danisrace_path_finding/01.jpg "Paps is driving Dani")
↩ Reply
Uno momento... ↩ Reply
In the Dani's Race Matrix Room Franzo said that when Petition for Version 2025-01-19 will reach 235 signatures, he will stream Dani's Race once again. It's already at 230. Make it happen! ↩ Reply
Anyway... ↩ Reply
Uno momento... ↩ Reply
In the Dani's Race Matrix Room Franzo said that when Petition for Version 2025-01-19 will reach 235 signatures, he will stream Dani's Race once again. It's already at 230. Make it happen! ↩ Reply
Anyway... ↩ Reply
↩ Reply
It should be simple, you say. Just use the Steering actuator inside of UPBGE, pair it with a basic Navigation Mesh and you are done. Wrong! As you maybe know Dani's Race Cars are not simple. And to control them properly ( as in: in a way that will not break the flow of the game ) is more tricky than that. ↩ Reply
I have to give the car specific control commands to accelerate, decelerate, how much to turn the front wheels and stuff. And the steering actuator does non of that. I though I was screwed. ↩ Reply
![[embedded image]](/pictures/danisrace_path_finding/02.jpg "Moria practicing the racetrack")
There was already one scene where you could see a character taking a car and doing something with it autonomously. Which wasn't a big deal anyway since even if it would fail, it would not actually impact the gameplay much. Still, the fact that I managed to make it work, made me feel like I could do that. ↩ Reply
This stunt in particular was accomplished in two stages. First a very simple path finding operation calculated the path of the car from outside of the racetrack to the inside of the racetrack. From which a different algorithm took over. Which is the racing algorithm I use for racing. But which is implemented smartly enough that I could use it manually for a specific car in a specific scene. ↩ Reply
![[embedded image]](/pictures/danisrace_path_finding/03.jpg "Navigation points")
Both of those methods used navigation points placed in different places, from which the cars could figure out where to go. For racing it was a rather straight forward thing to do. Just place enough of those checkpoints, make sure that they are all in order. And instruct the car to race as fast as possible towards one of them. And as soon as it reaches the checkpoint, make it go to the next one. ↩ Reply
This is the most basic algorithm that you can write. Well... Okay. I ended up spending a lot of time actually making it good. Making the cars know when to speed up and when to slow down. Making them see the road and obstacles. Teaching them the optimal racing lines. All of that had to be done at some point. You can look at the RacingAI function to see the extend of the insanity. But you get the point. You rotate the front wheels toward the target and accelerate. ↩ Reply
With a race it's not hard. It's literally a line. There is no path to find. But what about navigation through the town? Originally I was stupid enough to just bombard the town with bazillion points on each road, hoping that I can write something clever enough for cars to self-navigate themselves using those. But unfortunately it's not that simple. ↩ Reply
Path finding algorithms require you to have connections between points. And with my "just points" idea, everything was technically connected to everything else. There were no walls ever. The cars would attempt to cut through everything. Which did not resemble sanity what so ever. ↩ Reply
So I decided, since I have to figure it out for this scene to make sense, I will deal with it somehow. And so I made this: ↩ Reply
![[embedded image]](/pictures/danisrace_path_finding/04.jpg "Navigation mesh")
A navigation mesh made out of points, but with those points being connected together with lines, called edges. Giving me something with which I could maybe potentially implement a path finder algorithm. ↩ Reply
But then it struck me. ↩ Reply
Wait a second... Blender kind of has a path finder built into it. You can select a vertex and then with a control select another vertex. And guess what... Blender will select all of the vertices in between, finding the shortest path. And because UPBGE is technically blender under the hood. And because they finally figured out how to make
Let's go over it, line by line, what it does: We find our Navigation Mesh object. We deselect everything, so nothing will be technically selected in the blender side of things. We select out Navigation Mesh. And we make it active too. Blender has a weird way to make selection complicated. ↩ Reply
We go to the edit mode with that mesh. We deselect everything inside of that mesh. Then it's a little bit strange. We want to select our start and end points on the mesh. But for some reason you need to switch to Object mode when doing it. Anyway. We do that. We hop to the object mode, select our start and end points. Then hop back in. And do the magic part. We tell blender to select all vertices between the two selected ones. This gives us our path. ↩ Reply
Well... Actually... there is more code to sort those points. And more code to execute the path that was found. Both of which will be released at some point. But first 2025-01-19 should get released. Anyway... This way I can find a path made out of little checkpoints that now I can use, like in the race, to make Paps drive Dani to the karting club. Or anybody drive anywhere for any future scenes that I might need. ↩ Reply
Happy Hacking!!! ↩ Reply
![[icon unlike]](/icon/unlike)
0
![[icon left]](/icon/left)
![[icon right]](/icon/right)
![[icon terminal]](/icon/terminal)
![[icon markdown]](/icon/markdown)
It should be simple, you say. Just use the Steering actuator inside of UPBGE, pair it with a basic Navigation Mesh and you are done. Wrong! As you maybe know Dani's Race Cars are not simple. And to control them properly ( as in: in a way that will not break the flow of the game ) is more tricky than that. ↩ Reply
I have to give the car specific control commands to accelerate, decelerate, how much to turn the front wheels and stuff. And the steering actuator does non of that. I though I was screwed. ↩ Reply
There was already one scene where you could see a character taking a car and doing something with it autonomously. Which wasn't a big deal anyway since even if it would fail, it would not actually impact the gameplay much. Still, the fact that I managed to make it work, made me feel like I could do that. ↩ Reply
This stunt in particular was accomplished in two stages. First a very simple path finding operation calculated the path of the car from outside of the racetrack to the inside of the racetrack. From which a different algorithm took over. Which is the racing algorithm I use for racing. But which is implemented smartly enough that I could use it manually for a specific car in a specific scene. ↩ Reply
Both of those methods used navigation points placed in different places, from which the cars could figure out where to go. For racing it was a rather straight forward thing to do. Just place enough of those checkpoints, make sure that they are all in order. And instruct the car to race as fast as possible towards one of them. And as soon as it reaches the checkpoint, make it go to the next one. ↩ Reply
vect = car.getVectTo(checkpoint) turn = vect[2][0] Accelerate(car)
This is the most basic algorithm that you can write. Well... Okay. I ended up spending a lot of time actually making it good. Making the cars know when to speed up and when to slow down. Making them see the road and obstacles. Teaching them the optimal racing lines. All of that had to be done at some point. You can look at the RacingAI function to see the extend of the insanity. But you get the point. You rotate the front wheels toward the target and accelerate. ↩ Reply
With a race it's not hard. It's literally a line. There is no path to find. But what about navigation through the town? Originally I was stupid enough to just bombard the town with bazillion points on each road, hoping that I can write something clever enough for cars to self-navigate themselves using those. But unfortunately it's not that simple. ↩ Reply
Path finding algorithms require you to have connections between points. And with my "just points" idea, everything was technically connected to everything else. There were no walls ever. The cars would attempt to cut through everything. Which did not resemble sanity what so ever. ↩ Reply
So I decided, since I have to figure it out for this scene to make sense, I will deal with it somehow. And so I made this: ↩ Reply
A navigation mesh made out of points, but with those points being connected together with lines, called edges. Giving me something with which I could maybe potentially implement a path finder algorithm. ↩ Reply
But then it struck me. ↩ Reply
Wait a second... Blender kind of has a path finder built into it. You can select a vertex and then with a control select another vertex. And guess what... Blender will select all of the vertices in between, finding the shortest path. And because UPBGE is technically blender under the hood. And because they finally figured out how to make
bpy module run inside of the game itself. This meant I could do this:
↩ Reply
NavigationMesh = bpy.data.objects['NavigationMesh'] bpy.ops.object.select_all(action='DESELECT') NavigationMesh.select_set(True) bpy.context.view_layer.objects.active = NavigationMesh bpy.ops.object.mode_set(mode = 'EDIT') bpy.ops.mesh.select_all(action='DESELECT') bpy.ops.object.mode_set(mode = 'OBJECT') NavigationMesh.data.vertices[index1].select = True NavigationMesh.data.vertices[index2].select = True bpy.ops.object.mode_set(mode = 'EDIT') bpy.ops.mesh.shortest_path_select() bpy.ops.object.mode_set(mode = 'OBJECT')
Let's go over it, line by line, what it does: We find our Navigation Mesh object. We deselect everything, so nothing will be technically selected in the blender side of things. We select out Navigation Mesh. And we make it active too. Blender has a weird way to make selection complicated. ↩ Reply
We go to the edit mode with that mesh. We deselect everything inside of that mesh. Then it's a little bit strange. We want to select our start and end points on the mesh. But for some reason you need to switch to Object mode when doing it. Anyway. We do that. We hop to the object mode, select our start and end points. Then hop back in. And do the magic part. We tell blender to select all vertices between the two selected ones. This gives us our path. ↩ Reply
Well... Actually... there is more code to sort those points. And more code to execute the path that was found. Both of which will be released at some point. But first 2025-01-19 should get released. Anyway... This way I can find a path made out of little checkpoints that now I can use, like in the race, to make Paps drive Dani to the karting club. Or anybody drive anywhere for any future scenes that I might need. ↩ Reply
Happy Hacking!!! ↩ Reply
Find this post on Mastodon
![[thumbnail]](/pictures/thumbs/how_to_broken_cars.png)
![[thumbnail]](https://peer.madiator.cloud/lazy-static/thumbnails/e0d0e17f-84bb-4d51-b44f-b113b97c517f.jpg)
![[thumbnail]](/pictures/thumbs/night_light_hard.png)