thecraftychemist

thatscienceguy:

John Conway first theorized that it would be impossible to create a forever-expanding universe using these rules, which was proven wrong by a team at MIT, creating the “glider gun,” which is featured in the third gif. 

Since then, thanks to computers, people all over the world have added new designs to the database, creating amazingly complex designs.

For example Andrew J. Wade created a design which replicates itself every 34 million generations! Furthermore it is also a spaceship (permanently moving pattern) and not only that, it was also the first spaceship that did not travel purely diagonally or horizontally/vertically! These types of spaceships are now appropriately named Knightships.

The simulation has some interesting properties, for example it has a theoretical maximum speed information can travel. Or simply, light speed - as that is the limit in our own universe. The limit is set to 1 cell per generation - after all how can you create something further than 1 cell away in one generation if you can only effect your immediate neighbours? And yet you can get things like the ‘stargate’ (Love the name, huge SG fan here.) which allows a space ship to travel 11 cells in just 6 generations.

Some smart people have even designed calculators, prime number generators and other incredibly complex patterns.

You can create your own patterns here: http://www.bitstorm.org/gameoflife/

All gifs were made from this video: https://www.youtube.com/watch?v=C2vgICfQawE

deadreckoned
thepixelgeisha:

Indie or hobbyist, if you’re a game developer with a Tumblr blog dedicated to your process and progress, reblog this!
You will be added to The Game Developer Network.
You can read about the network here.
If you have a Twitter you’d like linked, please include that in your reblog!
You can also be added to the directory by messaging me.
** Remember: This is only for game developers.
Basically, my reason for creating this is so that gamedevs on Tumblr can find fellow gamedevs. It’s kind of like an easy to navigate directory to find and connect with people who are also working on games.
Don’t be scared to ask or reblog! This is for all game developers on Tumblr! Really. Don’t feel lame. Help me help you~
If you’re having trouble reblogging this post, here’s the direct link!

I had no idea this existed. Someday I’ll develop a game of my own and join… someday. For now, I can only reblogg it so it doesn’t get lost among the 234234234 likes.

thepixelgeisha:

Indie or hobbyist, if you’re a game developer with a Tumblr blog dedicated to your process and progress, reblog this!

You will be added to The Game Developer Network.

You can read about the network here.

If you have a Twitter you’d like linked, please include that in your reblog!

You can also be added to the directory by messaging me.

** Remember: This is only for game developers.

Basically, my reason for creating this is so that gamedevs on Tumblr can find fellow gamedevs. It’s kind of like an easy to navigate directory to find and connect with people who are also working on games.

Don’t be scared to ask or reblog! This is for all game developers on Tumblr! Really. Don’t feel lame. Help me help you~

If you’re having trouble reblogging this post, here’s the direct link!

I had no idea this existed. Someday I’ll develop a game of my own and join… someday. For now, I can only reblogg it so it doesn’t get lost among the 234234234 likes.

deadreckoned
deadreckoned:

Havenguard: DungeonBuilder
It’s been a while since I last posted something, so this is big one. Above is the abstract output of the new procedural DungeonBuilder for Havenguard. This is only one of many possible types of map builders within the game.
How does it work? Well, the concept is relatively simple, however the implementation starts to get complex when the ‘Room Graph’ (the green and purple nodes/connections) comes into play. Long explanation below, jump to the bottom for the TL;DR version.
What is the Room Graph?
Just a regular Graph data structure implementation (see links at the bottom for more information).
What is it good for? Awesome stuff. If we know how the level is structured, we can walk the graph from the starting room and do things like: Lock a door and make sure the key is placed in an ‘earlier’ room (easy!), add a mini-boss, epic loot chest, random event or NPC in a branch off the critical path or make sure that at least two-thirds of the way down the critical path a level boss is created. There are infinite possibilities, you just have to get creative!
It gives us a great degree of control over how ‘fun’ the dungeons are, as we can control the balance and pacing of monsters, loot, events, etc and can reward players for exploring the entire map, rather than just rushing from staircase to staircase.
How do we generate interesting Dungeons with it?
Let’s start at the beginning, with:
Room Generation
A Room class stores information about each room in the map (id, bounds, connections, etc).
Start by generating a single room anywhere within the bounds of the map. Give it an id and add to the room list.
Generate another room to either the left, right, top or bottom of the this room. If the room doesn’t fit (run the room bounds through a validation function), try again until a room is generated that does fit (to avoid an infinite loop, once a predetermined retry count is reached, the loop is broken and we just skip to the next step). Give it an id and add it to the room list.
Select a random room and repeat from previous step using the randomly selected room, until the maximum number of rooms are reached, or the failed placement counter reaches its limit.
Clip the map size to the extents of all rooms (this just reduces the amount of memory required to store the map, since we can dump a bunch of unrequired cells).
Dig out the rooms (this just sets the cell types within the room bounds to ‘Ground’, and their surrounding cells to ‘Wall’). Store the room ids on the Ground cells.
Done! That’s the easy part. We have a bunch of rooms, but they’re not connected…
Room Graph
Time to create the room graph!
The nodes within the graph represent a each room.
I also store a reference to the graph node on each Room object.
Once all the rooms are generated, we create a new node for each room and add it to the graph, in preparation for…
Corridor Generation
Pick a random room from the room list, set this to the ‘active’ room.
Find the closest room (distance from center to center) that currently has zero connections (rooms need to keep track of what rooms they’re connected to). This is the ‘target’ room.
Pick a random cell within each room.
Using an A* search with a special cost function (ask me about this if you want to know more), find a path between the two cells. Assert a path is found - If everything is working correctly, there isn’t a reason a path shouldn’t be found.
Step through the path, marking the current room id. We don’t dig out any cells here yet. If we encounter a wall, create and store (in a list or dictionary) a Door object at this location (Door class stores data for a door (location, state, locked, etc)).
Add any non-room/empty cells to a ‘to dig’ list.
Once we reach a Ground cell with a different room id, we know we’ve entered another room. We also know that these two rooms are connected - add an edge (a connection) to the graph between the two room nodes.
For the ‘cost’ for the edge, I used the number of empty cells between the rooms plus the area of the two rooms (width * height). This cost is used later.
Set the current room id to the newly entered room id, and continue to follow the path, repeating the above steps.
Once we’ve reached the end of the path, we have populated the edges on the Room Graph and we have a list of cells that require digging. Iterate over the dig list and dig out the rooms.
Set the ‘active’ room to the ‘target’ and repeat from step 2 until all rooms are connected.
Done! Now we’ve populated the Room Graph, marked our doorways, and dug out our corridors. Looking pretty awesome.
Doors
The next thing to do is validate all our doors. Even though we created them during the Corridor Generation step, not all of them are going to be valid. I have some rules for doors…
A door must be bordered by exactly two walls, strictly on opposite sides (north and south, or east and west).
A door must not be adjacent to another door on the straight axes (north, south, east, west). Diagonals are fine, but this is down to personal taste and how your levels are rendered. You could exclude diagonals too.
If a door does not satisfy these requirements, it is removed from the door list.
I also specify a ‘no door’ chance (a number between 0 and 1), which is rolled for each door using the RNG. If it rolls true, the door is removed from the list. This creates empty doorways, which you can do nice things with later (decorative archways, for example).
Room Graph Processing
The final step in the basic map generation (before we start populating it with monsters and sweet loot) is to process the Room Graph.
The Room Graph currently doesn’t do anything except tell us which rooms are connected to which and (approximately) how far they are from each other (the edge cost, remember?).
First we should decide on a starting room for the player. We could just pick a random room, but this would mean that rooms in the middle could be chosen too often, making the path to goal room too short.
I find the two rooms that are furthest apart, and then pick one of those two at random as the starting room.
From the start room, we begin walking the graph. I use a recursive function (a ‘visitor’) on the starting node, which then recursively calls itself on all un-visited neighboring nodes. You can see where this is going…
Each visited room stores its ‘Flow Index’ - this is a value telling us exactly how many rooms this room is from the starting room. The Flow Index starts at zero for the starting room, then each visited neighbor is the parent’s FlowIndex + 1. Because the visitor function is recursive, the value grows by one with each node visited. Beautiful. I also store the total ‘distance’ from the starting room (similar to the flow index above, but we use the edge cost we set above when building the graph). This tells us approximately how many cells there are between each room and the starting room (it’s not exact, but it’s a good indication).
There is other information you can store in this step, like: which rooms are dead-ends (no other neighbors), which rooms loop back onto another branch, etc.
Once all nodes have been visited, to find the ‘goal’ room of the dungeon (the downward staircase in a typical Roguelike), I simply find the room with the highest Flow Index and Distance from the start room. Simple!
To find the ‘critical path’ of the map (start room to goal room), just run the graph through A* to find the shortest path from the start room to the goal room.
Voilà! Now we have a completed Room Graph, which we can query for extremely useful information to control balance and pacing within each dungeon level, ultimately making a much more fun and rewarding experience for the player.
TL;DR
Generate your rooms and corridors, build a graph representing the connections between rooms, use the graph to place interesting ‘things’ within the dungeon, off or on the critical path (start to goal room). Use the graph to make the dungeon fun and interesting!
Useful Links
Wikipedia article on the Graph data structure: http://en.wikipedia.org/wiki/Graph_(abstract_data_type)
A very nice MSDN article on building a Graph data structure in C#: http://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx
Roguebasin articles on Roguelike concepts, with lots of examples: http://www.roguebasin.com/index.php?title=Articles
Amit’s A* Pages - lots of great information on the A* algorithm: http://theory.stanford.edu/~amitp/GameProgramming/
In fact, check out Amit’s excellent game programming information site: http://www-cs-students.stanford.edu/~amitp/gameprog.html

Cool! Reblogging for future reference.

deadreckoned:

Havenguard: DungeonBuilder

It’s been a while since I last posted something, so this is big one. Above is the abstract output of the new procedural DungeonBuilder for Havenguard. This is only one of many possible types of map builders within the game.

How does it work? Well, the concept is relatively simple, however the implementation starts to get complex when the ‘Room Graph’ (the green and purple nodes/connections) comes into play. Long explanation below, jump to the bottom for the TL;DR version.

What is the Room Graph?

  • Just a regular Graph data structure implementation (see links at the bottom for more information).
  • What is it good for? Awesome stuff. If we know how the level is structured, we can walk the graph from the starting room and do things like: Lock a door and make sure the key is placed in an ‘earlier’ room (easy!), add a mini-boss, epic loot chest, random event or NPC in a branch off the critical path or make sure that at least two-thirds of the way down the critical path a level boss is created. There are infinite possibilities, you just have to get creative!
  • It gives us a great degree of control over how ‘fun’ the dungeons are, as we can control the balance and pacing of monsters, loot, events, etc and can reward players for exploring the entire map, rather than just rushing from staircase to staircase.

How do we generate interesting Dungeons with it?

Let’s start at the beginning, with:

Room Generation

  • A Room class stores information about each room in the map (id, bounds, connections, etc).
  • Start by generating a single room anywhere within the bounds of the map. Give it an id and add to the room list.
  • Generate another room to either the left, right, top or bottom of the this room. If the room doesn’t fit (run the room bounds through a validation function), try again until a room is generated that does fit (to avoid an infinite loop, once a predetermined retry count is reached, the loop is broken and we just skip to the next step). Give it an id and add it to the room list.
  • Select a random room and repeat from previous step using the randomly selected room, until the maximum number of rooms are reached, or the failed placement counter reaches its limit.
  • Clip the map size to the extents of all rooms (this just reduces the amount of memory required to store the map, since we can dump a bunch of unrequired cells).
  • Dig out the rooms (this just sets the cell types within the room bounds to ‘Ground’, and their surrounding cells to ‘Wall’). Store the room ids on the Ground cells.
  • Done! That’s the easy part. We have a bunch of rooms, but they’re not connected…

Room Graph

  • Time to create the room graph!
  • The nodes within the graph represent a each room.
  • I also store a reference to the graph node on each Room object.
  • Once all the rooms are generated, we create a new node for each room and add it to the graph, in preparation for…

Corridor Generation

  • Pick a random room from the room list, set this to the ‘active’ room.
  • Find the closest room (distance from center to center) that currently has zero connections (rooms need to keep track of what rooms they’re connected to). This is the ‘target’ room.
  • Pick a random cell within each room.
  • Using an A* search with a special cost function (ask me about this if you want to know more), find a path between the two cells. Assert a path is found - If everything is working correctly, there isn’t a reason a path shouldn’t be found.
  • Step through the path, marking the current room id. We don’t dig out any cells here yet. If we encounter a wall, create and store (in a list or dictionary) a Door object at this location (Door class stores data for a door (location, state, locked, etc)).
  • Add any non-room/empty cells to a ‘to dig’ list.
  • Once we reach a Ground cell with a different room id, we know we’ve entered another room. We also know that these two rooms are connected - add an edge (a connection) to the graph between the two room nodes.
  • For the ‘cost’ for the edge, I used the number of empty cells between the rooms plus the area of the two rooms (width * height). This cost is used later.
  • Set the current room id to the newly entered room id, and continue to follow the path, repeating the above steps.
  • Once we’ve reached the end of the path, we have populated the edges on the Room Graph and we have a list of cells that require digging. Iterate over the dig list and dig out the rooms.
  • Set the ‘active’ room to the ‘target’ and repeat from step 2 until all rooms are connected.
  • Done! Now we’ve populated the Room Graph, marked our doorways, and dug out our corridors. Looking pretty awesome.

Doors

  • The next thing to do is validate all our doors. Even though we created them during the Corridor Generation step, not all of them are going to be valid. I have some rules for doors…
  • A door must be bordered by exactly two walls, strictly on opposite sides (north and south, or east and west).
  • A door must not be adjacent to another door on the straight axes (north, south, east, west). Diagonals are fine, but this is down to personal taste and how your levels are rendered. You could exclude diagonals too.
  • If a door does not satisfy these requirements, it is removed from the door list.
  • I also specify a ‘no door’ chance (a number between 0 and 1), which is rolled for each door using the RNG. If it rolls true, the door is removed from the list. This creates empty doorways, which you can do nice things with later (decorative archways, for example).

Room Graph Processing

  • The final step in the basic map generation (before we start populating it with monsters and sweet loot) is to process the Room Graph.
  • The Room Graph currently doesn’t do anything except tell us which rooms are connected to which and (approximately) how far they are from each other (the edge cost, remember?).
  • First we should decide on a starting room for the player. We could just pick a random room, but this would mean that rooms in the middle could be chosen too often, making the path to goal room too short.
  • I find the two rooms that are furthest apart, and then pick one of those two at random as the starting room.
  • From the start room, we begin walking the graph. I use a recursive function (a ‘visitor’) on the starting node, which then recursively calls itself on all un-visited neighboring nodes. You can see where this is going…
  • Each visited room stores its ‘Flow Index’ - this is a value telling us exactly how many rooms this room is from the starting room. The Flow Index starts at zero for the starting room, then each visited neighbor is the parent’s FlowIndex + 1. Because the visitor function is recursive, the value grows by one with each node visited. Beautiful. I also store the total ‘distance’ from the starting room (similar to the flow index above, but we use the edge cost we set above when building the graph). This tells us approximately how many cells there are between each room and the starting room (it’s not exact, but it’s a good indication).
  • There is other information you can store in this step, like: which rooms are dead-ends (no other neighbors), which rooms loop back onto another branch, etc.
  • Once all nodes have been visited, to find the ‘goal’ room of the dungeon (the downward staircase in a typical Roguelike), I simply find the room with the highest Flow Index and Distance from the start room. Simple!
  • To find the ‘critical path’ of the map (start room to goal room), just run the graph through A* to find the shortest path from the start room to the goal room.
  • Voilà! Now we have a completed Room Graph, which we can query for extremely useful information to control balance and pacing within each dungeon level, ultimately making a much more fun and rewarding experience for the player.

TL;DR

Generate your rooms and corridors, build a graph representing the connections between rooms, use the graph to place interesting ‘things’ within the dungeon, off or on the critical path (start to goal room). Use the graph to make the dungeon fun and interesting!

Useful Links

Cool! Reblogging for future reference.