Actually it's more like MK32 but as it's the second attempt at a working level builder I'll just stick with that.
Right now I've got a partially working version of the new level builder using the new prefabs. I'm glad I only made a few prefabs for testing as seeing them placed in the level has made me think a lot more about prefab design.
The level builder uses a simple BSP tree to designate areas of the map to contain prefabs. The it picks the best fit prefabs for that area. I choose a few and then randomly select one, I don't want to always use only the best fit as that will leave some prefabs unused and as such, wasted.
Here's a couple of examples with the BSP areas highlighted with different colors. There was a bug with these where it was in some cases choosing the smallest room instead of one of the biggest, but that's been corrected. One thing that jumps out at me about the prefabs is that they need more big and medium sized rooms. They also need to fill the space better. I'll have to work on that. It's worth noting that these prefabs are drawn from a relatively small sample of just 40 odd testing prefabs. I plan to have around two to three hundred prefabs in the final version of the game. I think too that there needs to be a better chance of choosing smaller prefabs sometimes, even if they don't quite fill the space. Only choosing the best fit is going to leave a lot of prefabs unused as I already said, but choosing too randomly will leave a lot of empty space.
In the above examples the levels are 25x25 tiles in size, but this may be reduced after play testing. Already some BSP leaves are left blank because they can't accommodate even the smallest prefab (minimum size is 3x3 tiles). I may write some code to leave others blank too to add some negative space in to the levels. Also these BSP trees are set up to have symmetrical depth. They are all divided up to a depth of 3 recursions, but it's easy to add a bit to the script to stop division part way. That might create a large prefab on one side of the dungeon and lots of small ones on the other. One possible idea is to have a level much larger than I need and have very high chances of blank leaves near the edge, scaling down to a 0% chance of blank leaves near the central area. this would avoid the obviously square layout of the levels seen above. Another idea would be to use the bigger level in the BSP drawing stage and then do a kind of cellular automata operation to create a more natural level layout, and then crop the level down to only the active BSP leaves.
Here's the script taken to an extreme:
You can set the size of the level just by changing one variable, and then set the maximum recursion of the BSP tree with another. If I wanted to create huge levels it would be easy. However, even the fairly basic experiments I did with the version 1 level builder, just navigating around the map, I found that a huge level is far from desirable.
There's still a lot of code to write for the level builder. It needs to select one or more of the BSP leaves as an exit point down to the next level, and I need to be able to integrate lower level sections from upper levels while building. Because some prefabs are 2 level prefabs, they extend in to the next level down. They need to be placed there and any BSP leaves they intersect have to be cut down so they don't overwrite the lower exit with another prefab. To deal with this I'll have to work recursively so each level is written affecting the next and each concurrent level takes those effects in to account as it is made.
As well as stairs it needs corridors to link the prefabs. I won't be using the traditional corridor building method used with BSP trees, instead each prefab has one or more "level hooks" which are where they will be joined to the rest of the level by corridors. They will have to find the shortest route between nearby level hooks while maintaining full connectivity, because long snaking corridors are just not that fun when over used.
I saw a nice script on rogue temple which gave me an idea about linking hooks in order using closest pairs and popping linked partners from an open list. I'll have to modify it, as I don't want prefabs with multiple hooks to link to themselves, but only to other prefabs. Anyway, that's the next step.
Another thing that needs doing is generating the walkable dictionary from the level dictionary. I also need to collect data about encounters and special events which is stored in the prefabs and port them over to a level event dictionary.
After all that is done I need to clean up the script and get ready to move it in to the main game file. I really feel the newer version of the level builder is light years ahead of the old one. It's great to be able to prototype something and then go back and make a better version of the system taking in to account everything you learned in the prototype. It's not as efficient as planning everything in advance, but to plan you have to know, and as this is my first time making a game like this, I simply didn't know how it would all turn out the first time. No doubt other aspects of the game will go through similar prototype--->working system process, it's unavoidable when doing something new for the first time. The really great thing about using the Blender game engine is you can prototype things really quickly and get really great visualizations right away. If something isn't working you can see it right there on your screen in vivid color, it really helps speed up the testing and building stage.
Right now I've got a partially working version of the new level builder using the new prefabs. I'm glad I only made a few prefabs for testing as seeing them placed in the level has made me think a lot more about prefab design.
The level builder uses a simple BSP tree to designate areas of the map to contain prefabs. The it picks the best fit prefabs for that area. I choose a few and then randomly select one, I don't want to always use only the best fit as that will leave some prefabs unused and as such, wasted.
Here's a couple of examples with the BSP areas highlighted with different colors. There was a bug with these where it was in some cases choosing the smallest room instead of one of the biggest, but that's been corrected. One thing that jumps out at me about the prefabs is that they need more big and medium sized rooms. They also need to fill the space better. I'll have to work on that. It's worth noting that these prefabs are drawn from a relatively small sample of just 40 odd testing prefabs. I plan to have around two to three hundred prefabs in the final version of the game. I think too that there needs to be a better chance of choosing smaller prefabs sometimes, even if they don't quite fill the space. Only choosing the best fit is going to leave a lot of prefabs unused as I already said, but choosing too randomly will leave a lot of empty space.
In the above examples the levels are 25x25 tiles in size, but this may be reduced after play testing. Already some BSP leaves are left blank because they can't accommodate even the smallest prefab (minimum size is 3x3 tiles). I may write some code to leave others blank too to add some negative space in to the levels. Also these BSP trees are set up to have symmetrical depth. They are all divided up to a depth of 3 recursions, but it's easy to add a bit to the script to stop division part way. That might create a large prefab on one side of the dungeon and lots of small ones on the other. One possible idea is to have a level much larger than I need and have very high chances of blank leaves near the edge, scaling down to a 0% chance of blank leaves near the central area. this would avoid the obviously square layout of the levels seen above. Another idea would be to use the bigger level in the BSP drawing stage and then do a kind of cellular automata operation to create a more natural level layout, and then crop the level down to only the active BSP leaves.
Here's the script taken to an extreme:
You can set the size of the level just by changing one variable, and then set the maximum recursion of the BSP tree with another. If I wanted to create huge levels it would be easy. However, even the fairly basic experiments I did with the version 1 level builder, just navigating around the map, I found that a huge level is far from desirable.
There's still a lot of code to write for the level builder. It needs to select one or more of the BSP leaves as an exit point down to the next level, and I need to be able to integrate lower level sections from upper levels while building. Because some prefabs are 2 level prefabs, they extend in to the next level down. They need to be placed there and any BSP leaves they intersect have to be cut down so they don't overwrite the lower exit with another prefab. To deal with this I'll have to work recursively so each level is written affecting the next and each concurrent level takes those effects in to account as it is made.
As well as stairs it needs corridors to link the prefabs. I won't be using the traditional corridor building method used with BSP trees, instead each prefab has one or more "level hooks" which are where they will be joined to the rest of the level by corridors. They will have to find the shortest route between nearby level hooks while maintaining full connectivity, because long snaking corridors are just not that fun when over used.
I saw a nice script on rogue temple which gave me an idea about linking hooks in order using closest pairs and popping linked partners from an open list. I'll have to modify it, as I don't want prefabs with multiple hooks to link to themselves, but only to other prefabs. Anyway, that's the next step.
Another thing that needs doing is generating the walkable dictionary from the level dictionary. I also need to collect data about encounters and special events which is stored in the prefabs and port them over to a level event dictionary.
After all that is done I need to clean up the script and get ready to move it in to the main game file. I really feel the newer version of the level builder is light years ahead of the old one. It's great to be able to prototype something and then go back and make a better version of the system taking in to account everything you learned in the prototype. It's not as efficient as planning everything in advance, but to plan you have to know, and as this is my first time making a game like this, I simply didn't know how it would all turn out the first time. No doubt other aspects of the game will go through similar prototype--->working system process, it's unavoidable when doing something new for the first time. The really great thing about using the Blender game engine is you can prototype things really quickly and get really great visualizations right away. If something isn't working you can see it right there on your screen in vivid color, it really helps speed up the testing and building stage.
ok, the coloured bsp pics look great - very clear. it's also clear where the problem lies: rooms
ReplyDeletelets assume you have a fresh bsp level with nothing allocated.
now decide how each area connects to other areas
for each area decide on whether it is a room, a corridor, needs to be removed, or special room
you can now construct each area from a set of prefabs adding doors if needed. in the above examples - think of all the additions as special rooms - these would be more complex with a puzzle, trap, flaming pit, etc :)
Thanks for the reply. I'll be dealing with it more over the next couple of days, you'll see it improve. More simple, large rooms will be part of the design but they've not been added to the prefab list yet.
Delete