Forums > General discussion
MapGEN v0.8.7.2
Thewolensheep:
There is this issue where if you press generate a random amount of times it gets stuck at "Generating..." when it says on the bottom that the map was generated in 0.2 seconds.
Plutonic:
Hmm interesting, will see if I can get it happening here.
Xrayez:
Plutonic, I really like it! It has been 3-4 years since I last posted here and during that time I have plunged myself into gamedev field. I'm developing a game inspired by W:A and I'm trying to implement a map generator.
If it's not a secret, I'd like to get some hints about the underlying algorithm you implemented:
* Are you generating maps from noise? You mention about interpolation.
* How do you texture grass?
* Also interested how objects could be placed, I guess you decide it based on pixel normals of some sort...
* RR generator is decent as well, I imagine you run some maze algorithm for that.This might all be not relevant for my use case because the actual collision shapes are generated from image via contour tracing algorithm.
So yeah, I'd like to know your opinion. ;)
Plutonic:
Hi! Happy to answer but don't have time right now, if I forget to do it later feel free to poke me!
Plutonic:
--- Quote from: Xrayez on December 17, 2018, 05:24 PM ---Plutonic, I really like it! It has been 3-4 years since I last posted here and during that time I have plunged myself into gamedev field. I'm developing a game inspired by W:A and I'm trying to implement a map generator.
--- End quote ---
Hey, it's looking pretty good! The rope and bazooka physics look pretty close to WA already.
--- Quote ---If it's not a secret, I'd like to get some hints about the underlying algorithm you implemented:
* Are you generating maps from noise? You mention about interpolation.
--- End quote ---
Nope, no noise in the standard island maps (though I do use noise in the SSR generator), the maps are made out of a selection of randomly (well, somewhat random, with some rules about how close to others they can be placed, and what areas they are allowed in) generated points, that are then ordered such that the lines between them don't cross and are then tessellated and interpolated to produce the final result. The interpolation in question is a Hermite Curve, as documented here:
http://www.cubic.org/docs/hermite.htm, though it is the tessellation stage that actually provides much of the shape. The tessellation algorithm went through MANY different versions, but the most recent is based on an image someone else in the community posted as a possible solution to making the maps nicer. So far I haven't had much luck finding it annoyingly, but if I stumble upon it I will post it again. But basically it involved adding new points in between two others at the mid-point, and then offsetting it perpendicular a randomised amount where the maximum allowed offset was restricted based on the distance between the original points, and it was not allowed to produce an overlap with the already existing lines.
--- Quote ---
* How do you texture grass?
--- End quote ---
This actually wasn't too tricky. The WA graphics provide an image of a small section of grass that tiles horizontally. In order to map it on to the generated map I split it up into as many images as the graphic is wide and then store them in an array. Then, for every pixel that is a "top edge of the map", we just place one of these 1px images on it (centered), where the modulus of the x co-ordinate is used to look up the correct image.
--- Code: ---GetGrassSliceImage(pixel.x % xGrassImg.width)
--- End code ---
--- Quote ---
* Also interested how objects could be placed, I guess you decide it based on pixel normals of some sort...
--- End quote ---
Urrrr, I probably *should* use normals. But it currently doesn't. And object placement is realy not all that great in MapGen to be honest!
The idea is basically:
1) Scan along the bottom of the object image and work out how wide the "base" of the object is, and where the middle of this base is.
2) Scan through all the edges of the map, look for areas in which the objects "base" would be entirely in the floor, and potentially there aren't other collisions with exisiting map/objects.
--- Quote ---
* RR generator is decent as well, I imagine you run some maze algorithm for that.
--- End quote ---
The RR generator is probably the one I am most proud of if I am honest, as while I didn't come up with the method myself, it took a LOT of reading / searching for something usable that provided the results I wanted - I think I was on the look out for solutions for a good 3 years or so!
My original version was indeed a maze generation algorithm, it would produce a basic maze, and then split the paths down the middle to produce a large loop. This works, but you get lots of back-tracking and a weird predictability to the maps, it also means that the start and end are always next too each other.
The current version is not a maze generation algorithm as such, and while I sort of remember the technique, not enough to explain it to someone else. I have managed to find the site that explained it well enough for me to work from at least: https://orden-y-concierto.blogspot.com/2014/12/unicursal-mazes-and-cavern-mazes.html
Hopefully that was helpful? If not, or you want to know more let me know and I will try my best!
Edit: Found the RR info, added it in!
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version