Dungeons, dungeons everywhere ...

Sometimes it comes to mind if placing every single tile by hand could be more time effective and yield a better dungeon. but it wouldn't be that much fun, would it?

At the moment i am also a little bit fed up with Eclipse Juno. I use Eclipse since i started programming, but it seems to get slower with every release. As well as eating tons of ram. I might downgrade to an older release until this is fixed.

But first i promised to explain how i actually generate those dungeons.

Generating dungeon like struktures, especially 2D is quite simple. the way i do it is by creating a integer matrix and seeding every field either full or empty using a noise function which is basically java.util.Random.

After all fields have been initiallized with what looks pretty much like white noise, i run multiple iterations of a cellular automaton over the matrix.

for every cell of the matrix i count the 8 cells around it as well as the cell itself. if 5 or more cells are solid, the processed cell turns or stays solid. if less then 5 cells are solid the cell itself turns empty.

5 to 8 iterations of this create a smooth dungeon without single pixels in the void or other artifacts.

now i have a beatiful dungeon that is nice to look at but useless in the context of solvability. The naive algorithm used to create the dungeon does not ensure that the dungeon is solvable e.g. you can move from point a to point b. There might be walls that make the dungeon unsolvable so we need an approach to fix this.

My first solution was to place 2 starting points in the dungeon. those starting points are placed at two fixed position depending on dungeon size. The position will then move randomly until the start and goal point fullfil two conditions. the first condition is that the start [ or goal point ] is in free space. The second condition is solid ground right under this point. 

This way the start and goalpoints _wiggle_ themselfes into position until those conditions are met.

Then i need to check wether the dungeon is solvable or not. This is done using a simple Astar implemenation.  My first attempt completly ignored heuristiks because i deemed them unneccessary to determine if the start and goal points are connected. Because of a flaw in my algorithm this didn't work and you can see the results  a few posts below. Luckily i found a few Astar implemenations on the internet and was able to bend it to my will. If the dungeon is not connected i simply generate a new one using the next seed i get from the PRNG.

Now i have a dungeon that looks nice and is connected. I fixed up a small routine to render those. I also added another cellular automaton that fills the dungeon with some vegetation. As of now it just places some entities on the map with a specific ruleset, but in the future i want to place those entities randomly on the map and then let the entities life. Water, for example, could pool up in certain areas, create moist places that lead to _shroomy_ surfaces on the ceiling or to grass growth etc. I have to get a few additional ideas what to add, but once you have an infrastructure to add those entities and then implement a simple ruleset how they behave, its quite simple to add more.

This way an otherwise sterile dungeon will look more organic and thus more believable.

I also have to work on the sprites, the grass texture, for example, is a placeholder i took from minecraft hoping i won't get sued before i replace it with something i can draw. I am also getting better at using Gimp.

In the end it pays off to write a little code rather then doing it all by hand. i can now generate dungeons that are virtually endless in size. the example pics are quite small, mostly because a browser would have problems displaying them otherwise and i have a very slow upload. Since google does not want 8192 x 8192 pictures uploaded to a blog, here are the dropbox links for anyone who wants them [ 0 , 1 , 2 , 3 , 4 ]  

Here are now some screenshots. Its in no way a game, those are just renders to a BufferedImage to test the dungeon creation algorithm. Maybe this turns into a game, we'll see.

If it does i think i found the right library to do the job. 

LibGDX looks awesome. Write code once and deploy it on any Desktop, Android and Browser, maybe even iOS soem time in the future. It also enjoys a very active developement [ making it hard to find an up to date tutorial ] and has great documentation.

Hope you enjoyed this. Good night :)

Finally

Now those are some nice connected dungeons :)

i will tweak the start point generation to be more _random_ but for now i like the results

A*Star fail

Hey,

just wanted to make a quick post, finally found some time for recreational programming again ^^.
Here is an implementation of the A*Star algorith WITHOUT heuristics.

this might still need some work. Its meant to be a cave generator for a plattformer at some point, but as you can see, its still a very early prototype consisting of a prng and a cellular automaton

Cleaning up!

The codebase grows and grows, and something that was once a test how i could render sprites in Slick2D has outgrown the "proof of concept" state, and is on its best way to turn into something more gamelike
So instead of introducing new features it was time for a refactor.
Package names now have a naming convention, so do classes. A logger has been introduces instead of all those System.out.println() as well as a config file that handles settings without the need to recompile the code. A friend was a great help, mostly because he works in a more professional enviroment then me, as well as more experience.

Another think i found was a true "first" in the java programming language.
Destroying an object explizitly in Java.
Apparently when using the Image Object from the Slick2D api, when you create an Image with a content, and then overwrite then content, the old content aparently still takes up memory, so if you rerender an image multiple times, you have a memory leak.
I use quite a nasty method to create the red [ now white, at a later point in color of owner ] overview in the right  upper corner.

Code

I am aware that this code is very bad code, in the beginning this was meant to test the galaxy generation algorithm, so it just created a image of the galaxy. But using it as a real time overview is very unressourceful, so this will change :)

I hope i find a way to render this in a better way, probably rerendering the image every time a star is changed ( owner or existence ), would be quite ok, because this happens rarely. the border and the view finder [ see other images ] will be rendered in the renderer thread with Shapes.

I will also try to get the Imagebuffer local, put everything in one method.

Till then have fun, and please, if you want, leave questions, opinions, suggestions etc.

has anyone ever heard of delaunay triangulation ?

if not, neither did i.
i friend who is working on a similar game pointed me in the right direction, so now i can finally generate vias, or starlanes without so much randomness. The algorithm allows me to have a guaranteed connection between all planets without to many and overlapping lanes. it works like a charm, but has pointed out another error i made when i first designed the game. I use an 2 dimensional array for all solarsystems. then i add a random displacement so my galaxy doesn't look like a huge 2 dimensional array. this means i still have overlapping vias, but the situation greatly improved.
The downside is that using this algorithm on 4000 points on a 512 x 512 matrix takes quite a while. I optimised the Galaxy creation quite a bit. so generating 4k solarsystems with ~ 9 planets each and vias takes 21125ms.
If i check how long the vias take, i get an impressive 20478ms. This means everything but the vias take 650ms to generate, then the algorithm eats solid 20 seconds.

I will post additional information later, i have to go now :)

-sascha

Now with more stars

As I had no motivation lately to improve the underlying game part of the game, i tried to make it more visually appealing. I started creating a background layer with stars. At first i used a simple sprite of a 3 x 3 cross as a star, but since i want most of the visuals to be generated and not saved, i decided to code them as well. I should add some gfx to the background as well, like fractal nebulas etc. but this has to wait. I also increased the resolution, fixed a bug i ha with opengl on my thinkpad t60 that caused the new vias [ the white lines ] and the orbs around the solarsystems to sometimes turn into large polygones rendered onto the screen completly messing everything up.

i like the look the game has now, but i am still missing a usable user input system and most of the game part as in buildings, research and spacecrafts, but this will hopefully be added at some point. i am currently thinking about switching from slick2d to using only lwjgl, mostly because 3d would look better and it would enable nice realtime lighting effects. but i am still not sure about this.

now some more pictures :)

Congratulations, its a game

As promised, some pictures. Finally something that looks like a game is emerging.

Building something finally works, although it completely ignores levels :D

The ugly lines  in the second picture are the vias that will at some point enhance transportation between solarsystems.

I am off for now, updates will follow ^^