How do I Connect random generated nodes together??

I created a simple way of generating nodes, but I can't figure out a way to connect them in a logical way.

Here's the capx of what I have for the nodes: https://www.dropbox.com/s/on1krbh60y58u ... .capx?dl=0

I'm going to use the first node as my start and the furthest away as my exit later on.

I want to get something like this:

So you want to make a FTL-like random star map with lanes?

Turns out this is actually rather difficult. Difficult but not impossible. Took me ~3 hours to figure it out and I have some experience with doing random generation in construct. The solution involves a fair deal of loops, functions and some array operations. Not sure if there are simpler ways to do this.

First of all you need your lanes to know to what they connect, I added A and B variables which store the ID of nodes which the lane connects. Connecting them in a sensible manner is the tricky part.

Basic idea was: generate nodes, after nodes are generated create lanes to 3 nearest other nodes, after all lanes are generated you delete duplicate lanes. To find the 3 nearest node you need an event sequence that for each node stores the distance to all nodes (including itself) in y=0 and the node ID at y=1 in an array's x element. Then you sort the array by axis X, go through elements 1 to number of lanes and create lanes to them.

Hardest part was deleting duplicate lanes actually. Took me an hour before I figured it out, the solution was surprisingly simple and short.

Linked capx with my solution below, right click-release generates new node set. Please bear in mind that it has 2 problems which you will have to figure out yourself.

https://www.dropbox.com/s/z9hlr5i169lnc ... .capx?dl=1

1) It is possible to generate node "isles" that are fully disconnected from other isles, the smaller the numbers of MaxLanes the more likely this is to occur. Wonder how the FTL guy solved this. He probably wrote code that checks if there is a path between the starting and ending node and created one if needed, that's the efficient solution. The lazy brute-force solution is to check if there is a path and if not generate the whole nodemap again.

2) Sometimes nodes overlap, this should not be too hard to fix. I would do a function for that after all nodes are generated but before you start generating lanes, that offsets overlapping nodes.

Also, compared to the image you attached, it has overlapping lanes. But that could be fixed some clever overlap checks, you would put lane in a family, check if the family object overlaps a lane object, mark for deletion (similar logic to removing duplicates).

wow thank you!

That's quite complicated, I'll look at it and try and learn as much as I can.

No wonder I couldn't figure it out

For problem 2 I have a solution for it that I used before.

Thanks again, I have a lot to digest!

Heavy.

https://drive.google.com/open?id=0B1SSu ... zEzNmVQcEU

99Instances2Go, holy wow, nice!

A clinic in functions!

You're using a lot of things I haven't seen yet, I'll be studying this also! Thanks!!

There must be a better solution. This has me caged.

I just cant find the logic in it. I thougt, if you break a link in two, and the middlepoint is closer to another node then to the starting node or the end node, then its a link that can be forgotten. It works that way, but that is a serious iteration.

I like what Pulsar has done, but as he says, it has a few little problems.

Same idea. Much better coded. Now the events effectively wait till the objects are created/destroyed.

I know when i can pick a newly created object.

I still have problems with conditions picking allready destroyed objects. Would ne nice if someone explained me the rules arround that.

https://drive.google.com/open?id=0B1SSu ... jg2b0NXUW8

Oh nice!

Would there be an easy way to limit the space between nodes? For example it would be nice to not have nodes close together.

I guess you could just offset them if the distance of a line is too short?

A second question, how do I make this static once it's generated?

For example, in a run I would need to generate 10-15 of of these on the start of the game and I would need access to these during the game.

I thought taking an image of them but that wouldn't work since I need the nodes to be clickable to select the map/mission etc.

Example:http://www.blazinggriffin.com/wp-content/uploads/2015/02/Galaxy-910x512.jpg

Each one of those nodes would be a generated map like you made.

Thanks

Yes Sir. MUCH easyer. Because they lay on a vertical shifted grid. The node-lanes are now predifined by that grid. As well as the nodes. Those are well organised, following strict rules too. There almost nothing random anymore.

Oh nice!

Would there be an easy way to limit the space between nodes? For example it would be nice to not have nodes close together.

I guess you could just offset them if the distance of a line is too short?

I managed to overcome that and get rid off lanes overlapping each other in the middle of space, see below capx. I have the events check if the distance to the closest node other than itself is less than 70 pixels. Then I have it offset the node and check again if any nodes are closer than 70 pixels to each other. Once no nodes are found I have it stop checking and moving nodes. There is a second way of avoiding the problem, it involves generating nodes inside grid sections and not allowing more than one node to be generated within a grid section. That requires different random node generation logic though. I may show how to do that later on.

Now I am stuck at checking if there is a path from start to exit. I have a function that marks all nodes connected to start, I know how to connect any "islands" if start is not connected to them. Problem is determining when the functions I did encountered a dead end as there are multiple instance of the connect function running in parallel.

https://www.dropbox.com/s/d0ltq4t9b6c1k ... .capx?dl=1

Regarding copying the FTL select sector map, you do two loops, one within the other. One is for the X axis the other for the Y axis. Next you generate nodes like this:

condition: mod(loopindex("x")/2)=1 action: set offset=100

condition: mod(loopindex("x")/2)=0 action: set offset=0

loopindex("x")*200,loopindex("y")*200+offset

I would show an example if I had the time, it is quite late and I am unfortunately rather busy tomorrow. Really want to solve that "node is connected" problem though.

Much Easyer. evillair

https://drive.google.com/open?id=0B1SSu ... ndrTjRUaXc

Pulstar, that's cool! Nice work!

99Instances2Go, yeah, that looks a lot easier! When I enter 10 for the variable How_Many_NODes I never get 10, I get a random amount under 10, am I missing something?

A second question, how do I make this static once it's generated?

For example, in a run of the game I would need to generate 10 of these on the start of the game and I would need access to these during the game.

A second question, how do I make this static once it's generated?

For example, in a run of the game I would need to generate 10 of these on the start of the game and I would need access to these during the game.

They already are static, so long as you do not run the generation events again or change layouts in game. Any loss of nodes on layout changes can be avoided by adding persistent behaviour to all randomly generated objects. You just need to remember that when you switch back to a layout all initial objects (stuff you place/see in the editor) will also be placed. So you need to check carefully if everything is where it should be and no new objects appear. Or worse, so you don't delete already existing nodes when deleting initial objects.

Alternatively, since you just need it for a map where you just pick it once every 5-15 minutes and do nothing else, you can have the sector branching map a separate layer above the fully random node map. Hide that layer when it is unneeded (FTL does this with the star map I think). However that approach has a different problem. You need to add some conditions to all clickable objects/nodes so that nothing happens when the branching map is visible or invisible. On clicked/touched events for invisible sprites to register.

Personally, as my current project is using lots and lots of window/screen for procedurally generated spaceships. I add a boolean to all button objects, if say ship weapons or ship cargo screens are visible (ship window button is set to true) I do not allow selecting a different ship to work as the ships are on a layer behind the window screens so you could click-through them.

If you go with the layer approach, I also recommend naming your layers and always using the string/text name in events (not the layer number), as adding deleting any layers of your project changes the layer number order and it becomes a chore changing all the numbers to the current ones and keeping track of them.

Thanks Pulstar for some good ideas!

Yeah, I learned quick to use naming strings for layer selecting

Thanks again, it's appreciated.

I solved the disconnected isles issues. Red lanes are lanes created by the gap-bridging logic I created:

Basically I added another boolean to nodes, which is only set to true after the connect function is fired for nodes connected via lanes to the initiating node. So if the number of nodes that are checked and the number of nodes that are connected is the same, but it is not equal to the number of total nodes, it means that unconnected nodes exist. Then I launch a "Pontifex" function that finds connected-unconnected node-pairs that have the least distance between their nodes. It retrieves two such pairs, creates lanes between them and lanes between the second least distant unconnected node, relative to the connected node of the pair. So 4 lanes per gap with two choke-points per gap. The overlap function may delete a lane or two, but it is guaranteed to create at least one lane per every gap (two for most).

It then goes back before the connection checking functions and runs them again. Once it finds that checked nodes=connected nodes=total nodes it stop running the generation logic.

https://www.dropbox.com/s/d1qsk715wkmtz ... .capx?dl=1