Creating great software, one line at a time


Quick level generation algorithm

Posted by Rowan Powell on July 18, 2015 at 5:00 AM Comments comments (0)

For my AI demo I needed a level for the player and the AI to face off inside which met a few simple criteria,

  • All places on the map can be reached from any other point
  • The map has a variety of open and more cramped areas
  • The map is complex enough in navigation that items have a reasonable distance between them and it's engaging to the player
After a bit of messing around with various approaches I was inspired to making something akin to this rougelike dungeon generator

So the algorithm I made has the following stages;
  • Generate some Room objects
  • Move them apart from each other so that they don't merge into larger rooms
  • Find rooms that overlap on an axis that don't have rooms between them that a connection would cross through
  • Make a connection between those rooms roughly in the centre of where they overlap on that axis
  • Put items and other decoration into the level
The creation of rooms and corridors naturally gives some smaller areas as well as any larger rooms, which works well for the type of level we want to create. but it is important that the rooms take up most of the space of our level, large empty gaps might mean we end up with unconnected rooms if they don't line up with any others. Rooms too spread out will also mean that the corridors become very long, which might work for singleplayer adventures but don't work very well when trying to find and engage in a 1v1 battle.

Using Java to develop an application using public libraries

Posted by Rowan Powell on July 9, 2015 at 2:15 PM Comments comments (0)

As part of my efforts to expand my ablilties, particularly with Java, I developed a small application in 6 hours over two days. The application uses freely available libraries on the internet to create a system that can recognise what a user is saying, check it for key search words and phrases and also search for relavent words around the spoken terms to find out if it's reasonable to flag the user up for further investigation.

The first part of the application is the hardest and least reliable as it's a problem that's been in the process of being solved for a very long time - speech interpretation. For my application I tried using IBM's Speech-To-Text service avaiable through the bluemix platform, but the system proved to be very difficult to use and had little in the way of guides for how to put together an application to make use of it. This was unfortunate because the service appears to be a lot higher quality than others on offer. I ended up working with Voce, which could be implemented as a .Jar library through Eclipse, significantly simpler. Unfortunately the Voce engine has some real issues in reliably detecting words and doesn't automatically use a dictionary.

The second part involved saving a log of what the user said to a file, whichwas fairly trivial as I had created a class to do this for a previous project (The client-server auction system needed a persistant data log).

The third part was trying to find if keywords matched sections of a body of text, this was also a really simple thing to implement as I had also already written a pair of functions that would check if a word could be made by insertions or deletions on the other word which can be found on my gitHub at which I've extended to take into consideration a maxmimum allowed edit distance, here I've just used 2 as a default value, but this could be easily made so that the function checks if the edit distance is less than 25% the length of the word or some other function. In my application I also disregarded words that were less than 4 characters as almost any word could be corrected to them.

The final part of the application required an analysis of google search results from a given term, this was made massively easier than it could have been by two factors. First, the analysis of the google search results could be done by applying the keyword contains functions I had used earlier. The second point was that a publically avaiable library GSon could convert JSon files into a readable format. Trying to read a normal google page is difficult as the results back tend to just be the display code for the page, not the actual search results. Instead a custom search engine was created (I actually used someone else's link) which returns all results in a JSON format, which could then be parsed by GSon and read by my program.

This was a really fun and challenging project to put together and really helped me to branch my skills out further, exploring the options available through public APIs and the various Libraries people have put together.

Line of sight detection algorithm

Posted by Rowan Powell on July 8, 2015 at 9:15 AM Comments comments (0)

The code used in this project can be found at

In a recent AI project I needed to work out how to check if the Agent could see locations on the map from where they were standing, taking into consideration the walls placed around the map.

The process of doing this was made significantly simpler by the fact that all obstacles to vision could be considered to be rectangles aligned with the axis, which reduces the neccessary maths by a considerable degree.

The first stage of the process attempts to disregard all non-relavent obstacles as they are tested, by doing a simple in-bounds test using a rectangle I could very quickly and efficiently throw away a large portion of the elements of the scene, this had the added benifit of excluding those that would be along the line of sight between two points but not between the two.

In the image above you can see how the process would take all relavent walls for a sight line between the red and blue locations, keeping all elements within the yellow bounding box and not considering any of those outside (Marked by a red cross) as able to block the line of sight.

The next step in evaluating if an object is going to block the line between two points is to consider it as a rectangle in this case and then break that rectangle into lines which can then each be assessed if they block the line at any point. A sample of how I implemented this for use in my agentCanSeePoint() function can be seen below;

As you can see, the mathamatics of the actual assesment is fairly simple, we just need to check if a line intersects the other line and if this intersection occurs within the bounds we described when we used a rectangle as the model for our obstacle. There are two edge cases for this calculation however, when the line being assesed is directly along one axis or the other, where the gradient is considered 0, Infinity or -Infinity, which is not helpful and leads to some buggy results, as such these have to be handled seperately in my implementation.

Overall though, this is a very simple function with enough modularity to be used extensively in the rest of the program. vectorIntersectsLine() can handle both horizontal and vertical edges to the boxes and then vectorIntersectsObject() can be used to make assesments of any object, moddeling it as a rectangle. This is then extended out in program as canSeePoint(X,Y) which takes into account all of the objects that block line of sight and disregards those outside of the relevant bounds, making for a very quick (in terms of written code) assesment of a line of sight.