General Coding » Polygon Pi

Unity Fence Layout tool

Games, General Coding, Unity 1 Response »

Feb 272020

I’ve published my first asset on the Unity Asset Store! Find it for free here: https://assetstore.unity.com/packages/tools/utilities/fence-layout-tool-162856

Or get the code directly from GitHub: https://github.com/AndyFenwick/FenceLayout

[EDIT: If anyone is interested, it’s had 142 downloads in the first five weeks after release. 29 in the first three days but it’s steadily getting a few each day since. That’s actually more than I was expecting.]

Fences

While making the Frozen game I wanted to put some fences down and assumed there would be a simple script on the asset store for this. There were a few fence tools available but they were all paid for. I’ve bought a bunch of art assets and tools (modelling definitely isn’t my strong point), but writing a simple tool to put a few objects in a line seemed like a perfect learning opportunity!

Here’s the tutorial video if you want to see what it does:

Writing the actual layout script was mostly simple. Add the prefabs, set up spacing, scaling and offsets, sample the terrain height and plop the prefabs down between the waypoints.

The only non-trivial part was dealing with uneven ground. On mostly flat ground the fences all line up nicely and look good. However on sloped terrain their disjointed and partially underground. The solution is to shear the fence model in Y so that both ends are on the ground. The only problem here is that Unity transforms don’t directly support shear. However there is a workaround by using two parent transforms and a series of rotations and non-linear scales. See this: https://answers.unity.com/questions/961330/shear-transformation-using-gameobject-transformati.html

I implemented that and it works well, with nice curving fences:

I’m not sure what happens to the colliders – the debug rendering becomes detached somewhat from the geometry, but it’s close enough that it works in my game so I’ve not investigated further.

Custom editor

The most fiddly bit was getting the custom editor and inspector working nicely in Unity. The input handling / selection handling stuff is pretty confusing – controls either wouldn’t consume input events, or they’d consume too many events and it would be impossible to select anything else. After some experimentation, this setup seems to work:

void InputUpdate(SceneView sceneview)
{
	Event e = Event.current;
	int controlID = GUIUtility.GetControlID(GetHashCode(), FocusType.Passive);

	if (e.control)
	{
		HandleUtility.AddDefaultControl(controlID);
	}

	if (e.type != EventType.Repaint && e.type != EventType.Layout)
	{
		GameObject fenceObj = Selection.activeObject as GameObject;
		if (fenceObj)
		{
			FenceLayout fence = fenceObj.GetComponent<FenceLayout>();

			// Do things with the fence...
		}
	}
}

public void OnEnable()
{
	SceneView.duringSceneGui += InputUpdate;
}

public void OnDisable()
{
	SceneView.duringSceneGui -= InputUpdate;
}

I also had various bugs with things not saving until I found out you have to manually set the object as dirty:

EditorUtility.SetDirty(m_fenceLayout);

And then found that editing a prefab still wasn’t saving. The fix for that was to mark the whole scene dirty if anything has changed:

if (EditorGUI.EndChangeCheck())
{
	EditorSceneManager.MarkSceneDirty(EditorSceneManager.GetActiveScene());
}

Have a look at the full code on GitHub to see the specifics.

Admin

I hadn’t quite realised the amount of admin that’s required to get something on the asset store. We publish enough apps in my day-job, but when you just want to publish a simple script it’s a bit of work to make (and work out what to put on) the required thumbnails, screenshots, social media banners etc. Plus write the documentation, record a tutorial video, write descriptions and all that. Good learning experience though.

Mirror game prototype

Computer games, Games, General Coding No Responses »

Aug 112014

It’s been a while since the last post, mainly because I’ve had two LAN parties in the last two weeks and getting my first Unity game prototype into a playable state has taken priority. But more about that one later. In the meantime, here is a prototype I made at the end of last year (complete with terrible programmer art).

Each player has an end zone area in their colour, and the idea is to place mirrors to direct as many of the beams into your zone as possible. You get points whenever the beams are going into your zone, and you can place bombs on other players’ mirrors to blow them up a few seconds later. First to 100 points wins. Here’s a three-player game:

Turns out that after playing it a few times, it’s not that fun. There is too much going on with mirrors popping up and disappearing all over the place, so beams change path unpredictably making it hard to plan anything. Originally there was limit to how often you could place mirrors or bombs, and the game became a manic click-fest. I then added a slight cooldown between clicks, but that was a bit frustrating.

The prototype was written completely from scratch in C++, apart from using ENet to make the networking side a bit easier. The reason for starting from scratch was purely that I wanted to have made some kind of playable game in this way, which I managed (but Unity is definitely the way forward from now on).

For the networking side of things I went pure server-authoritative to ensure there were no sync issues, and as a result it’s been almost entirely bug free. The client didn’t even know which player it was until near the end of development – it simply sends mouse clicks to the server, and the server sends back all the tile state updates. This is even the case when playing single player – the client and server run in the same process, and all communication goes through the network. This is a model I’m sticking with for all prototyping, because it means that if it works in single player it’s almost guaranteed to work multiplayer, which is makes debugging and testing much easier.

Unity networking and first impressions

General Coding No Responses »

May 302014

Everyone I know (for “everyone” = “programmers”, anyway) seems to be trying out Unity and I’d heard much praise about how easy it is for rapid prototyping. Enough to make me take a look.

My very first thought, going through one of the tutorials, was “this feels like cheating”. One of the basic tutorials is a vertical scrolling shooter, and within an hour or two you have 3D models, sounds, particles and some basic enemy waves. Creating it mainly involves dragging a few things around in the interface, and writing a few lines of code.

However, my next thought: this is so far removed from normal programming, how do I actually, you know, “make a game”? This is the bit I need to get my head around next, learning the proper ways to translate my normal C++ skills into the Unity paradigm.

Starting out with networking

My current game-making interest is for multiplayer LAN games (if you can’t find the perfect game, make your own!), so my first project was investigating the networking support and making a basic lobby. It didn’t take long to run into the first problem with the built-in networking solution, but more about that later.

There are two methods in Unity of networking your game. The first is to mark variables on objects as being synchronised, so that they’re automatically kept up to date across clients (e.g. position and rotation of characters). The second is to use Remote Procedure Calls (RPCs) which allow one instance of the game to call a function on another instance (to signal events, e.g. player has fired a weapon).

My preferred setup uses an authoritative server (the clients send inputs, and the server processes them and sends back the results) but the server is also a client so can play the game. This is as opposed to a dedicated server where you have a separate server process that all player clients connect to. Requiring a dedicated server for LAN play just seems messy and requires building and running two executables, which is a pain. Conceptually we have a separate client and server running in the same process, and all communication is through the network, even if it’s a single player game or your client is the server. The major advantage of this is that all clients run the exact same code and if the game functions correctly in single player then you’re confident it will work in multiplayer, which makes testing a lot easier.

Building a lobby

So the first thing you need is a lobby that allows you to create a server or join an existing one. Luckily Unity lets you do this in about three lines of code. The server then listens to connect and disconnect requests and assigns a player number to each connected player. Finally there’s a basic chat box so clients can all write in the chat window.

When a client connects to the server there’s a bit of back and forth with RPCs. The server sends an allow or deny response (in case the game is full or has been started), and on receiving an ‘allow’ response, the client sends back the player name. Once the server receives the player name that player is inserted into the lobby. To keep the code simple, the player creating the server goes through the same process as any other client – simply call the OnConnectedToServer event (client-side), and the OnPlayerConnected event (server-side) and all the message passing and player initialisation will happen exactly as if it was a remote client.

A very basic lobby

An RPC bug

This is where the problem comes in. An RPC has a parameter that determines who it is sent to: All, Server or a specific client. If your process is the server, and you send an RPC to Server, you would expect it to just call the local function. Instead it does… nothing! Which is really helpful, and means the client-running-on-the-server case doesn’t work.

This is a known bug and has been around for years. Reading forum discussions (such as this one) provides a good insight into the Unity community, where there are a bunch of people who will argue vociferously that this is in fact correct behaviour, and that all your code should look like:

if (Network.isServer)
  networkView.RPC("MyRPCFunction");
else
  MyRPCFunction();

I would respectfully guess that these people are unlikely to be professional programmers. Luckily it’s not too hard to fix. That same thread has a method of using reflection to write an RPC wrapper that does the correct thing: call the RPC as normal if you’re not the server, or look up the function by name and call it directly if you are.

There is a similar issue with instantiating objects. Depending on if you’re in a networked game or not, you need to use two different Instantiate methods. Adding a wrapper for this as well simplifies the code elsewhere. I guess that the ‘standard’ networking case these days that Unity was built for is dedicated servers, and I’m just old fashioned trying to build an old-style LAN game. But it can be done.

Some code

Here is my NetworkManager and Lobby code so far, which might be a useful starting point if you’re building anything similar:

UnityNetwork.zip

I’m not at all confident that this is the best way to go about coding in Unity, but it’s pretty tidy and works. You can create a named game, search for and join/disconnect/rejoin games registered on their test server or connect by IP, set your player name and chat in a box. The NetworkManager is a singleton class and the Lobby should be added to an object in the scene, and you should be good to go.

The only slight complication above using the standard RPCs is calling functions on a different script on the same GameObject. This “just works” using the standard calls, but when using the wrapper you need to pass in the target script. I guess the wrapper could search all the scripts, but you should know what script it’s in anyway so it’s probably not a problem:

NetworkManager.Instance.RPC(GetComponent<MyScriptName>(), "MyFunction", RPCMode.Server);

With all that out the way it’s on to the next step – start making an actual game.

Rolling Block Puzzle generator – uni dissertation (2002)

Computer games, Education, Games, General Coding No Responses »

Apr 182014

I recently dug up my university dissertation and related code, and was surprised that it still runs and isn’t as bad as I feared. It was pretty interesting at the time so I thought I’d share. It was a good call to choose a project in the games/puzzle area, as I’m pretty sure that helped me get my job in the games industry a few months later!

Full report, and running the code

RollingBlock.pdf – this is the full dissertation I submitted, in case you’re interested in reading about this in more depth.

RollingBlock.zip – this is the full source and compiled code, written in Java. I’ve not recompiled it since 2002 and some of the formatting seems a bit messed up, but it still runs (please don’t judge the code quality, this was my first reasonable sized coding project!). There is the full editor program, plus a variant on the player for puzzles with multiple moveable blocks.

To run the Editor program you need the Java JRE installed. If java.exe is in your path then editor.bat should launch the program, otherwise you’ll need to put the full path in.

Rolling Block Puzzles

The idea of the ‘rolling block’ puzzle is to roll a non-cube block (2×1 in the simplest case) through a grid-based maze so it ends up exactly covering the goal. Because the block isn’t square it takes up more room in some orientations that others, and the puzzle involves shuffling the block into the right orientation to get to where you want to go.

Here is an example puzzle, where you need to roll the blue block so that it stands upright on the yellow goal square. So the only possible first move is up-left, because there isn’t enough room to roll in the other directions:

This is a type of multi-state, or concealed path, maze. Underneath you’re navigating a state graph of moves from the start point to the end point, but the shape of the block, and the moves it allows, means that the actual path to the solution can’t easily be seen. There are only 53 empty squares on the grid but there are 125 reachable maze states, and the shortest solution requires 32 moves (solution at the bottom).

Automatic maze generation

These types of puzzles are very hard to design unassisted, because each block added or removed impacts the state graph in many different places. Some clever people design these things by hand, but us mere mortals can use a computer.

The first thing we need is a solver. This does an exhaustive breadth-first search of the maze and builds a graph of all states and the transitions between them. In each state there are at most four legal moves so it checks if each destination state is a duplicate, add a new node if it isn’t, and add an edge between the two nodes. Here is a very small 5×5 maze:

And this is the state graph a solver will come up with:

The numbers are how many moves are required to reach each state, so zero is the start position and 18 is the goal position (the colour coding is based on branches and dead ends). So you can see that even a tiny 5×5 maze with three obstacle blocks has quite a complex state graph.

Measuring puzzle quality

To generate good new puzzles, we have to be able to tell the difference between a good puzzle and a bad one. What makes a puzzle ‘good’ is a hard thing to pin down, but we can pull out a few ideas such as it having a long solution, many dead ends, looking deceptively simple etc. For our purposes though we need to come up with a single score for the quality of a given puzzle, such that a higher score means the layout is ‘better’ in some sense.

One approach is to analyse the graph that the solver produced, and score it using a weighted set of criteria. The criteria I used are:

Number of nodes – more states means a more complex puzzle
Solution length – longer puzzles tend to be harder
Number of branches – choices and dead ends are what make the puzzle interesting
Number of blocks – give this a negative weight to prefer simpler looking puzzles with less obstacles
Number of turns – requiring more direction changes can be a more interesting solution
Average loop length – large loops in the graph make it less obvious when you’re on the right path

Different weights can be assigned here depending on what characteristics you want in your generated puzzle.

A more interesting block – 60 move solution

Genetic algorithms

So now we can give a score to a specific puzzle, but we need to use this to come up with the best puzzle possible. For this we can use a type of genetic algorithm.

Genetic algorithms are based on the same principles as evolution in the real world: using randomness to slowly evolve towards an optimal solution. The idea is to start with a solution (any solution), and then randomly modify it a bit. If the new solution is better than the old one, keep it, otherwise throw it away. Repeat this process many times, each time starting with the best solution you’ve found so far. To tell if a solution is better than the previous one we apply a fitness function to see if it survives to pass on its ‘genes’ (or instead gets eaten by bears). After a while, you can stop the process and take the best solution found so far as your result. Despite what creationists may tell you, order can result from randomness (plus a fitness function).

In the case of a rolling block puzzle we start with either an empty board, or one with a few random blocks, and a mutation rate (maybe 5%). Each iteration we check every grid square to see if it ‘mutates’ (toggles between obstacle and empty). The fitness function is the puzzle score described earlier. If the score is higher or equal we keep it. Then just keep going as long as you want.

And that’s pretty much all you need to generate new puzzles. The key is the fitness function – the better it fits our subjective opinion of “this is a good puzzle”, the better the generated results will be. I’m sure that there are much better fitness functions out there but this one works well enough.

Here’s a video of it in action.

References

Robert Abbott’s Logic Mazes page

My multi-level puzzle applet hosted on Logic Mazes (probably won’t run with today’s security settings)

Erich Friedman’s designs

A bunch of mobile games using a similar puzzle

Example solution (L is up-left): LURDRDRDDDLLLULDRRRRULDLLLUUULUU

House layout/maze generator

General Coding 11 Responses »

Mar 122014

Now that I don’t make games for a living I find that I’m more inclined to do so in my free time. Nothing even approaching a releasable standard, but it keeps me amused, and is an excuse to mess around with network programming. Occasionally I’ll inflict a messy prototype on my friends at a LAN party, and I’ll probably write more about them here at some point.

For one prototype I needed some kind of random ‘house’ layout, with rooms and corridors and the like. Procedural maze generators seem to be one of those things that most programmers end up writing at some point, and as mine works reasonably well for what it is I thought I’d share it in case it’s useful for anyone. The code isn’t particularly efficient for large, deep layouts, but it’s quick enough for what I need it for.

The code

First of all, here’s the full code. I don’t think there are any external dependencies except for a RandBool() function, so it should pretty much compile (although I haven’t tested it stand-alone):

housegenerator.cpp , housegenerator.h

Here is a 50×40 tile layout that it generated:

houselayout

Each tile is brown for wall, orange for a room, grey for hallway, and the light crosses are the doors (I’m a programmer, not an artist…). Let’s see how it works.

The algorithm

I started from this pseudocode, referenced from this Stack Exchange question about house generation, and finished it off and made a few tweaks.

The idea is to generate a series of hallways and rooms, and add doors so that the layout is fully connected (every room is accessible from every other room). This is accomplished by repeatedly subdividing the space, first to create hallways, and then to create rooms. There are a number of stages:

Start by filling in the entire map with wall. We want to subdivide the entire map, except for the one-tile outer wall boundary, so initialise the queue of Areas with this.
While there are still Areas in the queue, take the front one and subdivide it. If we don’t have enough hallway yet (defined as a fraction of the final map being hall tiles) and the area is big enough, carve out a straight line for the hall and add the blocks on either side back into the queue. Otherwise, if the Area is big enough, cut it in two along a random line and add both bits to the queue. Otherwise, carve out the final room.
Now we have all the hallways and rooms, but they’re not joined. The next thing to do is connect the hallways to each other. Check the ends of each hall, and if there is more hallway the other side of the end wall, carve out the wall. All hallways are now guaranteed to be connected.
Now we need to put doors in. Add all the rooms to another queue of unconnected rooms. While the queue isn’t empty, take the first room and pick a random start point and work your way around the edge, checking if a door here would open onto a hallway. If so, place a door. If not, do the same again, except this time check for possible doors into rooms that are already connected (e.g. aren’t in the queue). If no doors were placed, re-add the room to the back of the queue.

And that’s about it. Eventually all rooms will have doors to either hallways or other connected rooms. Here are a couple more layouts:

Configurable options

There are a few variables at the top of the file that can be tweaked.

MaxHallRate. This is the fraction of the map that is allowed to be hallway. Set to 1.0 to keep subdividing until the individual rooms are too small to subdivide further. This will result is a very flat connection graph, where nearly all rooms are connected directly to a hallway. Set it to 0.0001 (not zero or it infinite loops) to create a single piece of hallway. The connection graph here will be very deep, creating more of a maze-like layout.
HallDoorProb. When a door is placed between a room and a hallway, this is the probability that more walls will be tested for creating additional doors. Set to 1.0 to always create doors in walls with hallway alongside, and 0.0 to only create one door.
RoomDoorProb. Similarly for doors to other rooms, this controls the probability of extra doors being created. Set both of these probabilities to zero to create a connection tree (with no loops) – there will only be one way of traversing doors to get from any room to any other room.
MaxRoomSize. This is the size below which rooms will no longer be subdivided. A bigger number mean bigger rooms.

From a house to a maze

Houses are generally well connected – it’s usually quick to get from any room to any other room, so there are often lots of doors or loops (except for my house, which seems designed to maximise journey times…). Mazes are supposed to be hard to navigate, with many dead ends and only one route through. Luckily enough, this algorithm supports creating both.

Hallways are the main backbone of the connectivity. Having many hallways greatly reduces the average number of doors that must be passed on any journey. Reducing hallways will make your layout more maze-like. You could remove all hallways entirely by modifying the start room to be of Hall type, but I haven’t implemented this.

Setting both door probabilities to zero will ensure the connected graph is a tree. This maximises the average number of doors traversed per journey.

Reducing the room size could be used to maximise the number of doors (although the layouts are less interesting with very small rooms.

Here is an example of a large maze-like layout I generated:

Enjoy solving that one!

Downloadable demo

If you want to play around with the generator but don’t have your own code to plug it into, here’s a Windows demo executable you can download:

http://35.170.75.192/files/HouseGenerator.zip

Disclaimer: This was written in my Mirror game engine, and is a quick hack-job to have something runnable. As such it starts and connects to a local multiplayer server, and requests network access. Feel free to deny access as it doesn’t do anything, but taking all that stuff out would have been a fair amount of work. Just so you’re aware.

There is also a bug with using hardware acceleration on some systems that I never got to the bottom of. So if HouseGen.exe doesn’t work, try HouseGen_warp.exe which uses a software renderer. The joys of PC development when you only have one machine…

Usage: Use the RunMe.bat file to edit the generation parameters (and change the .exe is required). The four generation parameters plus width and height are specified, and can be happily changed.