Classic Sonic-type gameplay isn’t really my focus, but the engine can already handle looping and be setup to work in 2D mode.
There will probably be a Sonic-ish section at some point for shit and giggle, but since I intend the game to be relatively moddable you should be able to make entire levels of it if you wish.
I try for A* but I’ve never really been able to get my head around that algorithm. probably just a math error somewhere. haven’t worked on it in years anyway. was trying to figure out client side automining in minetest.
What ? No.
It’s generated once when the level load and then everyone use it.
All NPCs get their info from the same node array, they just filter them based on their stats.
chunk boundaries.
*Shudder*
Yeah, chunk boundary issues are why I’m only working with one giant chunk for now. Especially since I want my levels to have significant verticality (castle, skyscrapper, etc) and having situations like most of the floor in one chunk and the stairs in an other would lead to paths that are nearly unsolvable.
then they get lost anyway because there’s a zillion possible paths and only a few good ones.
… what algorithm are you using ?
Mine is A*, with added Greed-first (much faster for a small risk of not picking the 100% best path) and hard-capped node exploration (pretty much mandatory on big maps otherwise they will explore ALL of it if the target is actually unreachable).
In my experience it’s extremely reliable.
oh, yeah that makes sense. you wouldn’t want a big thing pathfinding through a small space. still, that’s 380k nodes per map, per model. definitely want that “multi-chunk” thing if it’s an open world game.
I have trouble with those though, because if they’re static chunks, your pathfinding gets hung up on chunk boundaries. but if they’re centered on the model, then when the model moves, the array has to be updated, and so predicting a path, you also have to predict new arrays of possible positions with every step. it always ends up being less work to predict one possible position with every step, i.e. just using immediate collision detection.
so I just have the model try various paths with basic “what’s the easiest way to move” collision for their immediate surroundings, then pick the path that works the best. then they get lost anyway because there’s a zillion possible paths and only a few good ones.
Yeah, that’s grid-based pathfinding for you.
To give you an idea, the Gmod Ponyville map I’m doing my current tests on end up being a 380k nodes array (0.5m accuracy)
I will switch to a proper multi-chunk system if I ever decide to make the game open-world-ish.
immediate collision detection
Wouldn’t really work here as I want NPCs with different size, so the pathfinding algorithm need to know if the pony will fit before it even get there. Otherwise Celestia/TroubleShoes-sized characters would take paths they can’t actually complete.
oh, so it quantizes the positions, and has them crouch roughly around the right place. not sure if that’s the greatest idea since even divided up roughly that makes for a lot of possible positions in really big levels. can you have it only scan the geometry nearby the pony, like a big cube around them?
having a list of all positions would be handy if you had a lot of ponies all over the place though, since all their cubes would merge into the whole level anyway.
the few auto-repositioning algorithms that I’ve run into use immediate collision detection, rather than an array of all possible positions in space.
@redweasel
The pathfinding system scan the level’s geometry to make a rough list of all positions where a pony could fit. When it find one, it also check if there is some obstacles above, and how far.
So each position has a “ceiling height” value, that get checked against the NPC’s own standing/crouching height (since they won’t all be the same size). This way they know if they can even at all, and/or if they need to crouch to fit.
This should also be re-used for flying NPCs, but I haven’t started working on that at all yet.
Spoiler alert : it’s really not.
That video is nearly 2 months old, I’m still working on that goddamned Pathfinding.
In insight, I probably should have just gave up the few special features I wanted out of it and used Unity’s default one.
But eh, now it’s nearly ready. … except my computer half-died, so new devs are slowed to a crawl until I can buy a new one.
Never coded pathfinding myself, but I can easily imagine it’s nothing of the sort of easy.
Spoiler alert : it’s really not.
That video is nearly 2 months old, I’m still working on that goddamned Pathfinding.
In insight, I probably should have just gave up the few special features I wanted out of it and used Unity’s default one.
But eh, now it’s nearly ready. … except my computer half-died, so new devs are slowed to a crawl until I can buy a new one.
didn’t you have one of the earlier demos where she got the power up to run around a loop-the-loop without falling?
@Background Pony #5C91
your current filter.Classic Sonic-type gameplay isn’t really my focus, but the engine can already handle looping and be setup to work in 2D mode.
There will probably be a Sonic-ish section at some point for shit and giggle, but since I intend the game to be relatively moddable you should be able to make entire levels of it if you wish.
I try for A* but I’ve never really been able to get my head around that algorithm. probably just a math error somewhere. haven’t worked on it in years anyway. was trying to figure out client side automining in minetest.
It’s generated once when the level load and then everyone use it.
All NPCs get their info from the same node array, they just filter them based on their stats.
Yeah, chunk boundary issues are why I’m only working with one giant chunk for now. Especially since I want my levels to have significant verticality (castle, skyscrapper, etc) and having situations like most of the floor in one chunk and the stairs in an other would lead to paths that are nearly unsolvable.
Mine is A*, with added Greed-first (much faster for a small risk of not picking the 100% best path) and hard-capped node exploration (pretty much mandatory on big maps otherwise they will explore ALL of it if the target is actually unreachable).
In my experience it’s extremely reliable.
oh, yeah that makes sense. you wouldn’t want a big thing pathfinding through a small space. still, that’s 380k nodes per map, per model. definitely want that “multi-chunk” thing if it’s an open world game.
I have trouble with those though, because if they’re static chunks, your pathfinding gets hung up on chunk boundaries. but if they’re centered on the model, then when the model moves, the array has to be updated, and so predicting a path, you also have to predict new arrays of possible positions with every step. it always ends up being less work to predict one possible position with every step, i.e. just using immediate collision detection.
so I just have the model try various paths with basic “what’s the easiest way to move” collision for their immediate surroundings, then pick the path that works the best. then they get lost anyway because there’s a zillion possible paths and only a few good ones.
To give you an idea, the Gmod Ponyville map I’m doing my current tests on end up being a 380k nodes array (0.5m accuracy)
I will switch to a proper multi-chunk system if I ever decide to make the game open-world-ish.
oh, so it quantizes the positions, and has them crouch roughly around the right place. not sure if that’s the greatest idea since even divided up roughly that makes for a lot of possible positions in really big levels. can you have it only scan the geometry nearby the pony, like a big cube around them?
having a list of all positions would be handy if you had a lot of ponies all over the place though, since all their cubes would merge into the whole level anyway.
the few auto-repositioning algorithms that I’ve run into use immediate collision detection, rather than an array of all possible positions in space.
The pathfinding system scan the level’s geometry to make a rough list of all positions where a pony could fit. When it find one, it also check if there is some obstacles above, and how far.
So each position has a “ceiling height” value, that get checked against the NPC’s own standing/crouching height (since they won’t all be the same size). This way they know if they can even at all, and/or if they need to crouch to fit.
This should also be re-used for flying NPCs, but I haven’t started working on that at all yet.
Edited
See his other works on Derpibooru to find the other dev demos.
Never coded pathfinding myself, but I can easily imagine it’s nothing of the sort of easy.
That video is nearly 2 months old, I’m still working on that goddamned Pathfinding.
In insight, I probably should have just gave up the few special features I wanted out of it and used Unity’s default one.
But eh, now it’s nearly ready.
… except my computer half-died, so new devs are slowed to a crawl until I can buy a new one.
Edited