Tools Dev: The full saga
Overview:
My tool is a Roguelike Map Generation tool designed to create a map in the style of a roguelike using parameters set by the user to define its layout.
This post will be broken into several sections to talk about each of the following categories:
The Editor Utility Widget
Storing and organizing and transferring data outside of runtime
The Map Widget and creating the final map
Removing random nodes
Array topology
Setup of connections
Vetting the connections
Setup of the grid panel
20m Video breakdown
Reflection
The Editor Utility Widget:
The editor utility widget is set up as below.
I have made this widget as modular as I can whilst using abstraction to try and create a simple and easy to use input field for all the parameters that can be easily expanded as most of the fields are encapsulated in a scroll box so that its easy to update and add more features in the long term. Below is a list off all the buttons and how they work:
Update Current Node: This button will overwrite the data of the Selected Node with the data currently in the form
This works by setting the temp index to the current selected node and then updating the current node and combo box (as seen in the functions below) and then resetting the selected option to the temp index.
Set Node Image: This button will set the image of the Node Icon to the first selected Texture2D in the content drawer
When clicked it will run a get selected actors of class which will then get the first selected, check if its a texture 2d and if it is we will then set the node image to the selected texture
Create New Node: This button will create a new node with all the data currently in the form and add it to the selection box
When this is clicked it will add a new index into the array called Map content which is an array of struct type Map data as seen above. Once we do this we then set that array element's name, icon and can be first node elements to those currently active in the form then we add it to the combo box and set it to the selected option.
Delete Current Node: This button will delete all the data of the current Node selected and remove it from the selection box
When this button is clicked we get the index in the map content array that this corresponds to and remove it from the array then we update the combo box and set the selected option to the first option in the combo box.
Selected Node: This indicates the node currently selected and allows the user to swap between them
This is a blank combo box which is modified by other buttons and processes
Width, Length: These correspond to the width and length of the map with width being the number of rows and length being the amount of columns
These are just sliders that update their text boxes whenever their value changes and their value is stored into a data asset on destruct
Node Name: The name of the selected node
This is a text input field which is read by other buttons and processes
Node Icon: The Icon of the selected node
This is a blank image which is modified by the set node image button
Can be first node?: A Boolean to determine whether it can or cannot spawn in the first column of nodes
A Boolean checkbox that if checked allows the node to be in the first column
That's all the buttons and functions detailed. When you close down the widget it runs a destruct function which stores all the data gathered in a data asset.
Storing, organizing and transferring the data outside of runtime:
Originally I was going to try and store all the data in structs, interfaces and data tables but after a bit of testing I found out interfaces and data tables weren't really a good idea as its really hard to transfer and read from them outside of runtime so it just made more sense to use data assets. This is because you can read and write to them outside of runtime and they are a (in my opinion) much nicer and cleaner alternative to using data tables as I'm not the biggest fan of them.
The Map Widget and creating the final map:
From here on out is where things are going to get increasingly more complicated so I will do my best to explain how this works.
So the main bulk of the code is stored here within the map widget, it handles the entire sorting of the map, generation and vetting of the connections, removing random nodes and displaying it all on the grid panel.
To start with this is done by taking all the data we gathered from the editor utility widget and setting it to all of our relevant variables in the map widget and once all those have been set we then sort the data by its parameters, once that's complete we then create and resize the final map array of struct type FinalMap as shown below.
Struct:
IMPORTANT! - Its important to understand this struct to then understand what goes on later in the script. To clear up the less obvious ones FNode ConnectionNum is the amount of connections that node has connecting to it, FNode Connections is a Boolean array that holds all the outgoing connections from that node, it holds 3 indexes where index 0 is the connection that points up and right, index 1 points directly across and index 2 points down and right. Checker is just a debugging variable which doesn't affect the program and FNode Removed is to check if it has been removed during the random node removal process.
Sort First Nodes function:
In the above Sort first nodes function we loop through each node in final map, check if it can be a first node, if it can we add it to the first node array (which derives from the struct type below) and clear its connection array.
Once we have taken all the data out of the data asset we next want to resize our Map Nodes array and Wire Nodes array which are both arrays which hold the Node and Wire widgets respectively.
Wire Nodes Size:
The using a map size of (3, 4) as an example the above function is a way of returning the area showed below from the map width and length.
Now that we have setup all our arrays with blank entries and resized them to fit our specifications the next step is to actually fill them with the relevant data. The first step in this operation is to fill the Final map array with the first nodes which are derived from the First Node array we saw earlier.
This is done as seen above by looping through the final map array and setting the first columns nodes to random nodes from the first node array, note here that we set the FNode ConnectionNum here to 1 as we don't have any incoming connections to our first row and they are not holes so we don't want them to be flagged as holes during the vetting process later on.
We then set the rest of final map by getting random nodes from the node information array we set at the start.
and that's how we create our final map and fill it with data however this doesn't detail anything on how the wires are setup as that comes later in the setup of the grid panel.
Removing random nodes:
The current flow of operations goes as follows after we finish filling the final map array:
In this section I will cover how we remove the random nodes.
So first we get a random number between 2 and 4 (which will be exposed as a user parameter in the editor utility widget at a later date) and set that to a random number to remove. Once we have done that we then resize our counter array to this and run it through a for each loop (this was before I found out about the do n node). In the body of the for each loop we then set our local rand to a random index from the map nodes array that is valid and then we set that nodes opacity to 0 and set its FNode Removed to true.
Check for Valid Removal:
In this function we set the local index to the index we pass in then we loop through the local counter array (which is set to 3 as we are checking itself and its neighbours) we then check that index and its neighbours to see if the are already removed and that that index's neighbours don't have any removed. We do this because we don't want 2 nodes removed next to each other in the same column as this will lead to a dead-end being generated (a path that cant generate any valid connections). Once its looped round and found an index that has not been removed and its neighbours have not been removed it will then return that index as a valid index to be set in the remainder of the function.
Array Topology:
Before we get into how connections are generated its very important to understand the topology of the array and how the index communicate with each other to get their valid connections and neighbours. To start with Nodes can only connect in front of them and they cannot generate paths off the map or too removed nodes. To make a valid map these Nodes also adhere to a set of rules which is as follows:
Every node except the first row should have at least 1 connection running into it, it can have more than 1 but it should have AT LEAST 1, this is to prevent dead ends on the map as if a node has no connections then it is impossible for the player to traverse to it. The other rules are that edge nodes cannot draw a path to somewhere off the map, for example if the top edge node were to generate its connections it wouldn't be able to generate a path upwards, only down and across. The other rule is that there can be no crossing paths, meaning that if the node above has a path connecting it down right the current node can have a path connecting up left.
Below is a drawn example of the rules.
The first diagram is wrong because the last node on the first column has no lines connecting drawn, The second diagram is wrong because the edge nodes are drawing paths off the map and the third diagram is wrong because it has crossing paths.
Now that you understand the rules that these Nodes have to follow I will now explain index relations. What I mean by index relations is what number we need to add / subtract to our current index to get its neighbours, back facing connections and front facing connections.
The index relations are drawn below in a diagram assuming the circled node is the current node.
When translating to nodes in front we add the map width then add the modifier for that node (shown above on the diagram next to each node). When accessing neighbours in the same column we just add the modifier and when accessing nodes behind the current node we add the modifier to the map width and then multiply it by -1.
With all of this information hopefully you should understand the rules that the Nodes adhere to and how to translate the index across the map.
Setup of connections:
This is one of the most confusing sections of the tool as there are a lot of checks that need to be made based on a lot of different rules and index translations so I will do my best to explain how this works.
First we loop through the final map array and check if the current node is and edge node and pass it through to the generate connection function along with the index. The reason we need to check if its an edge node is because if we want to adhere to the second rule we want to make sure that our edge nodes don't generate off the map hence why we flag if its an edge node as we will need to call a different generation function for them.
Check Edge Node Function:
The check edge node function takes the index and takes it out of a zero base by adding one (as arrays are zero based elements and the map width isn't) then we do the modulo of the index with the map width, if this returns 0 then it means its an edge node and 0 is always an edge node and then we also want to do modulo on the zero based element as well to check for top edge nodes.
Now that you understand how we call the generate for each index we will now step into the generate function and step through each decision.
So first we set the index we passed in to the connection index variable and set it, the next step is to check if that index has been removed and if it has then if it has we branch again to check if that node was an edge node, if it wasn't we just pass and move to the next index but if it was we then check the Flipper Boolean (which is used to indicate whether its a top or bottom edge node) and invert it (if it was false set it to true and vice versa).
The next branch (branch 2) checks whether the current index is an edge node, if it isn't (meaning its a centre node) we then do another branch to check if the node above us has a right facing connection as if it does we then cant generate our full connection as if we do we could end up crossing wires. So if the node above has a right facing connection (if its connection array is true in index 2) we then run the generate bottom function which will randomly generate at least 1 connection (up to 2) with its centre and bottom connection as targets we then set this data and then increment the connection number. A similar process happens if it doesn't have a right facing connection coming in from above as it will run the same process but instead it will generate from all 3 directions instead of 2.
I will now briefly cover all of the generation functions here as they are quite lengthy.
Generate bottom:
With generate bottom we first clear our connection array and generate a random int from 1 to 2 and store it.
We then get the node that this connection would point to (as random int is the potential connection that this would point to) and we check if its been removed.
If it has we then check the random number that has been generated and set its opposite to be true as due to how we set up the random removals there will always be a valid connection somewhere meaning that if 1 is invalid 2 will be valid.
If the node hasn't been removed we then set the random int's connection and then we loop through and randomly generate the other connection with a 50% probability.
Generate top works the EXACT same way but instead we replace every instance of 0 in this code with 2 instead and vice versa.
Generate Centre:
We essentially check if the node ahead has been removed and then we loop through based on bypass and setup the connection array.
Generate Full:
Generate full is the most complex as it has to run a lot of checks to make sure everything its doing is valid but it starts of the same as all the other functions.
It will check if its "guaranteed" connection (random int) hasn't been removed and then loop through and generate the rest of the connections randomly whilst also checking if the node being connected to actually exists.
If the guaranteed connection has been removed it will then attempt to generate another guaranteed connection using the same method as before in the above and below screenshots.
The above screenshot will run if it on both other times the node it tried to access was returned to as removed, and all it does is find the only available connection and connect to it.
While we are here I will also show the increment connection number function:
What this function does is it takes the current index and will loop through each of its connections in the connection array and translate that to the modifier needed to access the relevant index that its connecting to the if there is a connection it will get the index of that node and check its in range of the map and if it is we will then update its connection number and increment it by one.
Now that we have gone through all the relevant function we will get back on track with the generating connections so on the 2nd Branch if we did return an edge node we return true and then we branch again on a check that the previous node was not an edge node and that if that node had a right facing connection. If it returned false on that branch we then know its just a generic edge node and then we run set top or bottom depending on a branch out of flipper and we then increment the connection and invert flipper.]
Lastly if it returned true for having a right facing connection and it not being an edge node then all we need to do is generate a centre connection, increment the connection number and invert flipper.
And that's everything for how the connections are generated, I understand that was a bit complicated but that's as hard as it gets mostly.
Vetting the connections:
Now that we know how the connections are generated we want to loop through the array and check there aren't any "Holes" where a hole is a valid index without any connections going in. So to do this we loop through final map and add any indexes to an array if their connection number is equal to zero and they are NOT removed. Then we run the plug holes function with the array of nodes with no connections.
The next step is to loop through missing holes and clear the available connections array each time whilst running the plug le hole function passing in the array element from the missing holes array.
When we run the plug hole function we first need to set some variables with the first being the index of the hole to plug then we set our Local modifier to ignore to -100 so its safely out of range (as -1, 0 and 1 are all valid cases so we need to make sure it doesn't interact with those).
The next step is to check whether the hole is an edge node, and if it is we then need to check its type and then we set our modifier to ignore based on its edge type.
The next step is to loop through the counter array (which will happen 3 times) then we calculate our modifier by manipulating the array index and then we do a branch to check whether our modifier and our modifier to ignore are the same. If they are then we do nothing else we check if the node accessed by the modifier (which will be one of the 3 nodes behind) has been removed if it has we do nothing, if it hasn't we then add it to an array of available connections. This will loop through 3 times and it will fill available connections with at least 1 connection.
The next step is to get a valid index from this list as if we pick a random one we run the risk of breaking rules such as crossing wires so first we set a bool called Right Facing? to false then we loop through available connections and we check if any of them have a right facing node and if they do we store it as a hit index and break out at the first right facing connection and we then do a branch based on whether a right facing index was hit, if it was we connect the indexes using the hit index as the from index and the hole as the to index. If we didn't find any right facing connections we just return a random one from the available connections and connect that to the hole.
Work out relation:
Connect indexes will clear the connection array and it will work out the relation between the index from and to and then it will join the 2 nodes with a connection and then it will increment the hole connection number by 10 (this was just for debug so I could tell if a hole had been plugged or not).
And that's the logic behind plugging holes, the logic for this really stumped me for around a week. I tried making it originally and that led to the need for a lot more variables and functions so it led to me jamming a lot of things on the end which probably was the reason it didn't work. In the end I decided to entirely scrap the original code (Which can be seen in the code dump post a few posts back) and just remake it from scratch which was actually super helpful as it gave me the opportunity to clean up a lot of my code and make it neater (yes I know some of it looks disgusting but that's due to how large the struct is and it cant really be helped as you cant pull specific values out of a struct without splitting the whole struct wide open).
Setup of the grid panel:
Now we are almost there, at this point in time all the connections have been generated and validated so our final map is ready all it needs to do now is to spit it out onto the widget.
The first step for this is to setup the grid boundaries and to do this we first need to setup some variables.
First we resize our width (row) and length (column) to *2 - 1 this is because if we want to also add wires in we need double the map size - 1 was we don't want wires hanging off the bottom.
For example a (3, 4) grid would look like this:
Nodes Highlighted:
Wires Highlighted:
As you can see (3, 4) translates to (5, 7)
Once we have resized our counter array we then loop through and set the row and column fill of the grid panel with the Variables Ccount and Rcount ever approaching zero as 1 will sometimes be bigger than the other so we want to know when to stop setting that field.
Once we have setup our column and row fill we now want to start assigning widgets to these slots.
The first to be added are the wire nodes.
Return Row Column (Wires):
We make sure to set our temp width and length to certain values before running it so our return row column function runs correctly. As for the return row column function its a tad complicated to explain so ill just leave it to you if you want to try and work it out from the image above. But essentially its purpose is converting a wire index into a row and column for it to slot into.
Next we do the same but for the actual nodes themselves.
First again we set all our temp variables to specific values and set current wire search point to 0. Next we loop through final map, get the map node widget corresponding to the current index, set its image to the node icon, add it to the grid using the return row column function and then we check if the wire nodes search point hasn't exceeded the wire nodes size which we showed earlier and then we set the wires from the node we are referencing currently.
Set Wires:
The first branch is for debugging so ignore that but the 2nd branch checks if the current index has been removed and if it has it will then check if its an edge and then its edge type and then adjust wire search point accordingly.
If the node hasn't been removed we then set our connections, the current index and the column length. Next we check to see if the current index is an edge node and if it is we will then check its edge type and then we will loop through 2 times and resolve the wire based on the index and current connections. If it isn't an edge node we loop through 3 times instead
Resolve Wire:
Resolve wire simply gets the connection checks if it exists and if it does it will then set the relevant wire image based on the wire index.
And that's it that's all the logic, thank you for reading if you got this far I do realize that it was a lot of ground to cover and a lot of fairly complicated topics but that is essentially how my tool works inside out.