Game Development Guides and Resources for Those Who Need It

godot won, bevy trannies lost
godot is only 50mb btw
1727420297582555.png
 
Pathfinding

1697906624612.png

Getting an agent to navigate a space may be one the the greatest challenges for any programmer with enough gall to accept it. The amount of bullshit you have to account for is insane, it's no wonder most people use prebuilt solutions. But to honor a specific use case I decided to attempt tackling the challenge on my own.

I decided to go with a flowgraph (or something approximating it) reasoning being the algorithm would be easier to implement and it would scale well with higher number of units (as compared to A* which calculates the path for each unit individually). The downside is that the computing time grows with map size more so than unit count, I figured it was a worth while deal so I proceeded.

The graph is made up of points, each point knows it's own neighbours (cardinal and diagonal). That's all they know, nothing else. I figured working like this would make for an elegant solution, not having to bother with storing the whole grid of their positions or anything, all they would need is an array of their neighbours (technically 2), don't even need to know which direction those neighbours are in!

But then, how do I get a path to a point? Simple: Every point has a reference to another point called "direction". From this, the destination point simply takes all it's neighbours and sets their direction to be itself (the destination). Now all of the points around the destination are "pointing" to the destination. After this, each of these points do the same to their neighbours, and then those points do the same to their neighbours etc. This creates a sort of wave of points, stepping further away from the destination and direction the outer points towards the center. It is an elegant solution in the sense that the algorithm is exceedingly simple, I added some additional logic to make it prefer cardinal connections over diagonal connections just to make corridors not crowd one edge.

Imagine my surprise when calculating a flow graph took MULTIPLE SECONDS. That's intolerable, so I went to see what I can mend in the code. First, I replaced one of the lists with arrays, this just about cut the time in half (as expected from previous experiences, NEVER USE LISTS). After this I decided to try changing up the algorithm slightly. At first , in order to get this wavy behavior, I had implemented a static queue (first-in-first-out list) where I would add each newly "directed" point and take out the point which was done "directing". I figured an alternative would be making a static delegate function that would trigger a function of every point, this function would then check if the step (the index of the wave or whatever you wanna call it) belongs to the wave currently being calculated. This is basically a function that gets run on 300 points for every point, so yeah, you do the exponentially increasing math. YET SOMEHOW STILL It was faster than using a single fucking queue. <- have a load of this shit. This brought me to about 60ms to calculate a flow graph of 300 points. Not great but probably tolerable with multithreading (not that I know how to do that), I then tried doubling the points to 600 and got a computing time of 350ms. This is what we call exponential suffering. Adding more points not only means more points need to be calculated, but that every calculation is more demanding due to the function that is being called on every single point. The function itself isn't demanding for any point not in the current wave, for most points it's just an integer comparison. But evidently, doing 600 integer comparisons 600 times gets a little fucking demanding.

Well at least it seems like it would have a simply solution, minimize the amounts of times this function is being called. I tried to do this by dynamically subscribing the function to the delegate only when it needs to be called, and unsubscribing it when it's no longer needed. BUT THIS MADE IT WORSE! It went to about 380ms! I guess the delegate's list of subscribers is itself some sort of list, so any gains I get by not calling the function unnecessarily get trumped by editing the list.

(none of this is including the garbage time which increases the computing time by about 70~80% [angry])

I was hoping to somehow bandaid a way to "block" certain directions (this would kinda ruin the elegance because I would have to start checking for positions), so I can make certain corners sharp, or even add cover, but I highly doubt I can do that with the current atrocious performance. There's other little peculiarities like figuring out when a path is no longer being used and disposing of it and what not, but one foot after the other, kinder.

At this point I'm shit out of ideas for optimizing this thing. I was hoping to have thousands of points for the paths but I dread even attempting something like that. The performance hit wouldn't be as drastic if the graphs were divided into two, because the exponentiality decreases, so that's a silver lining for whatever use case that would fit.

I do plan to rewrite this into ECS code (entity component system) which should make it a lot faster or some shit, but I would first need to learn ECS, as well as learning multithreading for ECS for deterministic multiplayer and I do not like the sounds of that one bit

(mind you I still haven't tackled the actual navigation agent AT ALL)


If anyone is interested I can share the code, it's basically a single class with some 200 lines of code (elegance or something). Would be great if anyone had a clue as to what gear could be greased for better performance.

now excuse me as I go back to stare at it and ponder
 
Spasoje's Revenge said:
Pathfinding

View attachment 47547

Getting an agent to navigate a space may be one the the greatest challenges for any programmer with enough gall to accept it. The amount of bullshit you have to account for is insane, it's no wonder most people use prebuilt solutions. But to honor a specific use case I decided to attempt tackling the challenge on my own.

I decided to go with a flowgraph (or something approximating it) reasoning being the algorithm would be easier to implement and it would scale well with higher number of units (as compared to A* which calculates the path for each unit individually). The downside is that the computing time grows with map size more so than unit count, I figured it was a worth while deal so I proceeded.

The graph is made up of points, each point knows it's own neighbours (cardinal and diagonal). That's all they know, nothing else. I figured working like this would make for an elegant solution, not having to bother with storing the whole grid of their positions or anything, all they would need is an array of their neighbours (technically 2), don't even need to know which direction those neighbours are in!

But then, how do I get a path to a point? Simple: Every point has a reference to another point called "direction". From this, the destination point simply takes all it's neighbours and sets their direction to be itself (the destination). Now all of the points around the destination are "pointing" to the destination. After this, each of these points do the same to their neighbours, and then those points do the same to their neighbours etc. This creates a sort of wave of points, stepping further away from the destination and direction the outer points towards the center. It is an elegant solution in the sense that the algorithm is exceedingly simple, I added some additional logic to make it prefer cardinal connections over diagonal connections just to make corridors not crowd one edge.

Imagine my surprise when calculating a flow graph took MULTIPLE SECONDS. That's intolerable, so I went to see what I can mend in the code. First, I replaced one of the lists with arrays, this just about cut the time in half (as expected from previous experiences, NEVER USE LISTS). After this I decided to try changing up the algorithm slightly. At first , in order to get this wavy behavior, I had implemented a static queue (first-in-first-out list) where I would add each newly "directed" point and take out the point which was done "directing". I figured an alternative would be making a static delegate function that would trigger a function of every point, this function would then check if the step (the index of the wave or whatever you wanna call it) belongs to the wave currently being calculated. This is basically a function that gets run on 300 points for every point, so yeah, you do the exponentially increasing math. YET SOMEHOW STILL It was faster than using a single fucking queue. <- have a load of this shit. This brought me to about 60ms to calculate a flow graph of 300 points. Not great but probably tolerable with multithreading (not that I know how to do that), I then tried doubling the points to 600 and got a computing time of 350ms. This is what we call exponential suffering. Adding more points not only means more points need to be calculated, but that every calculation is more demanding due to the function that is being called on every single point. The function itself isn't demanding for any point not in the current wave, for most points it's just an integer comparison. But evidently, doing 600 integer comparisons 600 times gets a little fucking demanding.

Well at least it seems like it would have a simply solution, minimize the amounts of times this function is being called. I tried to do this by dynamically subscribing the function to the delegate only when it needs to be called, and unsubscribing it when it's no longer needed. BUT THIS MADE IT WORSE! It went to about 380ms! I guess the delegate's list of subscribers is itself some sort of list, so any gains I get by not calling the function unnecessarily get trumped by editing the list.

(none of this is including the garbage time which increases the computing time by about 70~80% [angry])

I was hoping to somehow bandaid a way to "block" certain directions (this would kinda ruin the elegance because I would have to start checking for positions), so I can make certain corners sharp, or even add cover, but I highly doubt I can do that with the current atrocious performance. There's other little peculiarities like figuring out when a path is no longer being used and disposing of it and what not, but one foot after the other, kinder.

At this point I'm shit out of ideas for optimizing this thing. I was hoping to have thousands of points for the paths but I dread even attempting something like that. The performance hit wouldn't be as drastic if the graphs were divided into two, because the exponentiality decreases, so that's a silver lining for whatever use case that would fit.

I do plan to rewrite this into ECS code (entity component system) which should make it a lot faster or some shit, but I would first need to learn ECS, as well as learning multithreading for ECS for deterministic multiplayer and I do not like the sounds of that one bit

(mind you I still haven't tackled the actual navigation agent AT ALL)


If anyone is interested I can share the code, it's basically a single class with some 200 lines of code (elegance or something). Would be great if anyone had a clue as to what gear could be greased for better performance.

now excuse me as I go back to stare at it and ponder
Click to expand...
Alright, you're not going to believe what just happened.
Get this, the actual computing time for the graph was 30ms, the rest? Well the rest went away after I got rid of all the debug.logs. Yeah, the debugging took 10 times longer than the actual algorithm. Isn't that a fucking riot? Man, life is such a grand ol' time.
 
BlenderChud said:
geg gegdot money went to some tumblr whore
View attachment 47517
oreoreviewshow said:
godotsisters... it's fucking OVER
View attachment 46702
Click to expand...
Click to expand...
BlenderChud said:
godotxisters?
github.com

GitHub - bruvzg/gdsdecomp: Godot reverse engineering tools

Godot reverse engineering tools. Contribute to bruvzg/gdsdecomp development by creating an account on GitHub.
github.com github.com
Click to expand...
Okay. Now. I know I have supported Godot a lot in the past, but now, I don't think I can do that anymore.
blenderchvd fvcking won.... it's over...
sad neutralplier.png
 
Spasoje's Revenge said:
Pathfinding

View attachment 47547

Getting an agent to navigate a space may be one the the greatest challenges for any programmer with enough gall to accept it. The amount of bullshit you have to account for is insane, it's no wonder most people use prebuilt solutions. But to honor a specific use case I decided to attempt tackling the challenge on my own.

I decided to go with a flowgraph (or something approximating it) reasoning being the algorithm would be easier to implement and it would scale well with higher number of units (as compared to A* which calculates the path for each unit individually). The downside is that the computing time grows with map size more so than unit count, I figured it was a worth while deal so I proceeded.

The graph is made up of points, each point knows it's own neighbours (cardinal and diagonal). That's all they know, nothing else. I figured working like this would make for an elegant solution, not having to bother with storing the whole grid of their positions or anything, all they would need is an array of their neighbours (technically 2), don't even need to know which direction those neighbours are in!

But then, how do I get a path to a point? Simple: Every point has a reference to another point called "direction". From this, the destination point simply takes all it's neighbours and sets their direction to be itself (the destination). Now all of the points around the destination are "pointing" to the destination. After this, each of these points do the same to their neighbours, and then those points do the same to their neighbours etc. This creates a sort of wave of points, stepping further away from the destination and direction the outer points towards the center. It is an elegant solution in the sense that the algorithm is exceedingly simple, I added some additional logic to make it prefer cardinal connections over diagonal connections just to make corridors not crowd one edge.

Imagine my surprise when calculating a flow graph took MULTIPLE SECONDS. That's intolerable, so I went to see what I can mend in the code. First, I replaced one of the lists with arrays, this just about cut the time in half (as expected from previous experiences, NEVER USE LISTS). After this I decided to try changing up the algorithm slightly. At first , in order to get this wavy behavior, I had implemented a static queue (first-in-first-out list) where I would add each newly "directed" point and take out the point which was done "directing". I figured an alternative would be making a static delegate function that would trigger a function of every point, this function would then check if the step (the index of the wave or whatever you wanna call it) belongs to the wave currently being calculated. This is basically a function that gets run on 300 points for every point, so yeah, you do the exponentially increasing math. YET SOMEHOW STILL It was faster than using a single fucking queue. <- have a load of this shit. This brought me to about 60ms to calculate a flow graph of 300 points. Not great but probably tolerable with multithreading (not that I know how to do that), I then tried doubling the points to 600 and got a computing time of 350ms. This is what we call exponential suffering. Adding more points not only means more points need to be calculated, but that every calculation is more demanding due to the function that is being called on every single point. The function itself isn't demanding for any point not in the current wave, for most points it's just an integer comparison. But evidently, doing 600 integer comparisons 600 times gets a little fucking demanding.

Well at least it seems like it would have a simply solution, minimize the amounts of times this function is being called. I tried to do this by dynamically subscribing the function to the delegate only when it needs to be called, and unsubscribing it when it's no longer needed. BUT THIS MADE IT WORSE! It went to about 380ms! I guess the delegate's list of subscribers is itself some sort of list, so any gains I get by not calling the function unnecessarily get trumped by editing the list.

(none of this is including the garbage time which increases the computing time by about 70~80% [angry])

I was hoping to somehow bandaid a way to "block" certain directions (this would kinda ruin the elegance because I would have to start checking for positions), so I can make certain corners sharp, or even add cover, but I highly doubt I can do that with the current atrocious performance. There's other little peculiarities like figuring out when a path is no longer being used and disposing of it and what not, but one foot after the other, kinder.

At this point I'm shit out of ideas for optimizing this thing. I was hoping to have thousands of points for the paths but I dread even attempting something like that. The performance hit wouldn't be as drastic if the graphs were divided into two, because the exponentiality decreases, so that's a silver lining for whatever use case that would fit.

I do plan to rewrite this into ECS code (entity component system) which should make it a lot faster or some shit, but I would first need to learn ECS, as well as learning multithreading for ECS for deterministic multiplayer and I do not like the sounds of that one bit

(mind you I still haven't tackled the actual navigation agent AT ALL)


If anyone is interested I can share the code, it's basically a single class with some 200 lines of code (elegance or something). Would be great if anyone had a clue as to what gear could be greased for better performance.

now excuse me as I go back to stare at it and ponder
Click to expand...
what lang are you using?
 
BlenderChud said:
try o3de
Click to expand...
it looks like a piece of shit tbh and besides from that it's disappointing seeing the current state of godot but I think I'm going to continue to use godot, because I'd rather not spend loads of time learning an entirely new engine from scratch just because godot went woke. I'm not gonna go make my own game engine either or use g3n on golang because other engines might not have the features that godot has and I'd rather just stick to what I know at this point.

In the future, I might have to use go for projects that demand absolute performance but having to build an engine from the ground up, implementing animation trees and shit yeah fuck that, that can kill itself, that can fuck right off. And fucking memory pointers? What the fuck. O3DE reeks of some unreal engine type bullshit.
 
Soygoy said:
it looks like a piece of shit tbh and besides from that it's disappointing seeing the current state of godot but I think I'm going to continue to use godot, because I'd rather not spend loads of time learning an entirely new engine from scratch just because godot went woke. I'm not gonna go make my own game engine either or use g3n on golang because other engines might not have the features that godot has and I'd rather just stick to what I know at this point.

In the future, I might have to use go for projects that demand absolute performance but having to build an engine from the ground up, implementing animation trees and shit yeah fuck that, that can kill itself, that can fuck right off. And fucking memory pointers? What the fuck. O3DE reeks of some unreal engine type bullshit.
Click to expand...
finally a sane soygoy take, who cares if a tranny leeches of Godot. The engine is already usable and in a state to produce games with ease. Even if it's only downhill from now, it has a lot of momentum.
>memory pointers
I never heard anyone refer to pointers like that geg
 

Similar threads

C
Serious I need a 3D swede model for my video game
Replies
2
Views
92
Starbing_Artiste
Starbing_Artiste
XXX_SKIBIDISIGMA_XXX
Chud Learning shooter game skills: 360 noscoping
Replies
0
Views
87
XXX_SKIBIDISIGMA_XXX
XXX_SKIBIDISIGMA_XXX
FrogKing
give me ideas for a game
Replies
6
Views
195
LordThrembo
LordThrembo
Soygoy
  • Locked
Autism Project Punishment / Fundamental Punishment - a Fundamental Fangame
29 30 31
Replies
602
Views
11K
Steve
Steve
Rot
Project Soyduel The Game
2
Replies
23
Views
1K
rubberbugging
R
Back
Top