We’re rewarding the question askers & reputations are being recalculated! Read more.
4 replaced http://stackoverflow.com/ with https://stackoverflow.com/
source | link

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* to link the rooms together. But this has some paths go straight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to properly connect the rooms without going through already existing connections/rooms.

But how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms and create a complete graph from this and then apply the Delaunay Triangulation.

I've never done anything with graphs before. So what I would to know is a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

[small edit]after some more looking around stackoverflow i found this post explaining Graphs more in depth. http://stackoverflow.com/questions/15306040/generate-an-adjacency-matrix-for-a-weighted-graphhttps://stackoverflow.com/questions/15306040/generate-an-adjacency-matrix-for-a-weighted-graph

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* to link the rooms together. But this has some paths go straight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to properly connect the rooms without going through already existing connections/rooms.

But how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms and create a complete graph from this and then apply the Delaunay Triangulation.

I've never done anything with graphs before. So what I would to know is a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

[small edit]after some more looking around stackoverflow i found this post explaining Graphs more in depth. http://stackoverflow.com/questions/15306040/generate-an-adjacency-matrix-for-a-weighted-graph

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* to link the rooms together. But this has some paths go straight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to properly connect the rooms without going through already existing connections/rooms.

But how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms and create a complete graph from this and then apply the Delaunay Triangulation.

I've never done anything with graphs before. So what I would to know is a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

[small edit]after some more looking around stackoverflow i found this post explaining Graphs more in depth. https://stackoverflow.com/questions/15306040/generate-an-adjacency-matrix-for-a-weighted-graph

    Tweeted twitter.com/#!/StackGameDev/status/373054103590813696
3 added 205 characters in body
source | link

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* to link the rooms together. But this has some paths go straight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to properly connect the rooms without going through already existing connections/rooms.

But how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms and create a complete graph from this and then apply the Delaunay Triangulation.

I've never done anything with graphs before. So what I would to know is a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

[small edit]after some more looking around stackoverflow i found this post explaining Graphs more in depth. http://stackoverflow.com/questions/15306040/generate-an-adjacency-matrix-for-a-weighted-graph

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* to link the rooms together. But this has some paths go straight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to properly connect the rooms without going through already existing connections/rooms.

But how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms and create a complete graph from this and then apply the Delaunay Triangulation.

I've never done anything with graphs before. So what I would to know is a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* to link the rooms together. But this has some paths go straight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to properly connect the rooms without going through already existing connections/rooms.

But how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms and create a complete graph from this and then apply the Delaunay Triangulation.

I've never done anything with graphs before. So what I would to know is a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

[small edit]after some more looking around stackoverflow i found this post explaining Graphs more in depth. http://stackoverflow.com/questions/15306040/generate-an-adjacency-matrix-for-a-weighted-graph

2 edited with more information. thanks for telling me!
source | link

I'm trying to learn procedural generation technique's. Specifically for dungeons. I have a mapstarted off with rooms i randomly createa 2D array and i gotI generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* setup nicely to make corridorslink the rooms together. But i want tothis has some paths go one step further and usestraight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to determine which rooms areproperly connect the rooms without going through already existing connections/rooms.

TheBut how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms already have their centerpoints stored and tiles have a cost assigned for A*. Now.. Ive takencreate a look at wikipediacomplete graph from this and googled some. Butthen apply the examples i found speak of using edges to calculate thingsDelaunay Triangulation.

Any tips, examples or reading materialI've never done anything with graphs before. So what I would to know is greatly welcome!a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

I have a map with rooms i randomly create and i got my A* setup nicely to make corridors. But i want to go one step further and use Delaunay Triangulation to determine which rooms are connect.

The rooms already have their centerpoints stored and tiles have a cost assigned for A*. Now.. Ive taken a look at wikipedia and googled some. But the examples i found speak of using edges to calculate things.

Any tips, examples or reading material is greatly welcome!

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* to link the rooms together. But this has some paths go straight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to properly connect the rooms without going through already existing connections/rooms.

But how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms and create a complete graph from this and then apply the Delaunay Triangulation.

I've never done anything with graphs before. So what I would to know is a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

1
source | link