![]() ![]() If we assume that the lines in the minimum spanning tree (green lines) are the hypotenuse of a right angle triangle then we can use formulas, created by smarter people than me, to find the length of the both the opposite and adjacent sides of the triangle. To do this we need to think back to trigonometry, but more specifically right angle triangles. Next we need to create corridors from the minimum spanning tree. The lines in green make up the minimum spanning tree. The lines that create the Delaunay triangulation come from the center of the rooms. This means that we need to find the minimum amount of lines it would take to connect all the rooms. The lines in pink make up the Delaunay triangulation.įrom the Delaunay triangulation we need to create a minimum spanning tree. Put simply this is just creating a series of lines that connect all of the rooms without any overlapping. We need to create a Delaunay triangulation of the currently active (grey) rooms. The next section is a little complicated so I used an open-source library to do the difficult stuff for me. The rooms are then aligned to the maze ‘grid’ meaning that their positions will always be multiples of 1. We will then relocate all of the rooms so that the average position of all of them is the exact center of the world, the xyz coordinates for this are (0, 0, 0). These rooms are now referred to as active rooms and are grey as opposed to pink. We then need to choose some rooms to create the maze with, generally speaking rooms that have an area that is higher than the average area of all the rooms are good. This distribution should be a bell curve.Īfter we have some rooms we need to separate them. The positions of the rooms should be random within the grid however, it’s best if they are weighted so that the majority spawn near to the middle whilst fewer spawn close to the edges. Then we need to generate some rooms, these should also have a random width and height however, they should not be square. ![]() This should have a random width and height. To start we have to create a grid in which to put all of our map items in. In between screenshots I will be needing to restart the map generation so the example maps that are built are always going to look different, however, you should still be able to see what is happening. The creator of Tiny Keep, Phi Dinh, explains this algorithm much better than me in a post on reddit. Map Generationīefore I start explaining this section I would like to state that my map generation is heavily inspired, and is very similar to, another dungeon generation algorithm from the game ‘Tiny Keep’. I won’t be explaining the full algorithm here as there are plenty of better resources for that. From this it can extrapolate a path of nodes (usually just positions on the grid) that lead you from the source to the destination. This A* pathfinding algorithm operates on a grid (it doesn’t always have to), it first picks one position as a starting point and one position as a destination. This is the completed path from a source to a destination on this grid. You can also see a series of smaller black squares with black lines connecting them. The grey squares are walkable and the red squares cannot be traversed. The squares represent a grid on which the A* algorithm can operate. In this image you can see a few things going on, let me explain. Especially since the maze is built on a grid structure.īelow is an image depicting the visual representation of the pathfinding in the mini-game. With almost the same efficiency of Greedy Best First Search (GBFS) and the reliability of Dijkstra’s algorithm it is clearly the best choice for pathfinding through this maze. The pathfinding algorithm is a basic implementation of the A* pathfinding algorithm that is so popular in game development. The first is the map generation script and the second is pathfinding so that the enemy can find the player. In the creation of this maze mini-game there are two main systems. Morgan worked on the other two games and together we worked on the rest of the games code. My contribution to the project was mainly the 3D dungeon crawling game. Since there were so many members working on the same project we had to split up the work. I was the first programmer and Morgan james was the other. In my team for this project we had two designers and two programmers. This project requires 3 separate monitors and 3 separate windows compatible controllers to be played. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |