Sunday, September 18, 2016

Green Algae: Dev Update pathfinding

Finding the way

So just implemented a brute-force pathfinding method implementing a basic Flood-Fill (Breadth first search) algorithm. It's wasteful but effective. I plan to improve the pathfinding method to a more practical implementation for use in other areas. It's enough to get started integrating it more abstractly into the basic game world for easier use when characters want to move around. It was pretty fun seeing it work.

Other work

On top of the pathfinding, I reworked the map generation which is hopefully more efficient, reliable, and is making more evenly distributed islands. If you noticed from previous screenshots the islands were all generating on an angle moving to the top-left while generating. Was due to the infamous off by one error, though I was kind of digging the realistic nature of some of the island strips. Perhaps that could be a useful generation permutation in the future.

Where's the build?

I wish I had something playable that you could check out but it's just too rough right now. And I do not have any process for putting together a public release yet. But things are moving along getting some basic AI and decision making system set up is probably my number one priority. Once I have a solid extendable task based system for controlling units assignments it will open the gates to adding all kinds of content. Right now it's just reworking and molding the current code into a more effective structure.

Suggestions welcome

By the way the game concept is very much flexible at this point in time. Not much at all has been solidified. That being said, I am completely open to suggestions or ideas that you may have to help guide some of the gameplay. 

Comments to any update post or to the Project Page are strongly encouraged.

P.S. You can find updates to the Roadmap on the project page. I'll get a description of the game there too since there is no dev version yet.


Wednesday, September 14, 2016

Green Algae: Frontiersman Development Update

Yay! We struck tree!

Things are moving a little bit after fixing up a number of things. Rearranging stuff implementing some additional stuff as well. Like being able to select objects on the map and get details about them.

Trees can be selected and designated to be chopped down. Currently only a single object selection is available. I'll put drag and drop selection on the roadmap of course.

So here's where things stand.
  • Terrain
    • finish tile-type transitions
    • add dirt (with transitions)
    • add gravel (with transitions)
    • add random stones
  • Player controls
    • map movement controls
    • object-selection and displayed details new
    • designating actions for map items
      • chop/down tree
      • stockpile area designation
  • AI Simulated Character
    • add gender and age new
    • add basic decision-based model
    • add crappy path-finding method
    • add hunger, starvation, and death
    • add actions and event, thoughts and memory
  • Save/Load
    • Test, test, test
  • Build Scripts and release checklist

Sunday, September 11, 2016

Green Algae: Game Development Update

Update: Tile transitions

Finally got transitions built between grass sand and water. I still think there are a few edge cases that need to be handled like one water tile surrounded by sand and other combinations of the same.

My first approach which quickly became a painstakingly brutal experience reloading map after map. Note to self create a small map test area. Was to have different tile types for each transition tile for instance a SAND_WATER_TOP_LEFT this became problematic when working with a testing tile types in the game logic. For instance player collision with water, and placing bridges. Not to mention that determining which transition to place was also difficult things kept breaking as more and more tile types were added. So I decided to use a slightly more subtle approach.

While rendering each tile the adjacent tiles are tested to determine which transition is to be used. This method short-circuits only testing each north, south, east, west, northeast, southeast, northwest, southwest, position in turn if any fail the test exits. These are mapped to the corresponding image for the transition changing which image is rendered.

Focus on gameplay

For the moment I think I need to focus on getting as many gameplay elements working as possible to actually have something that can be played like a game. Currently there isn't any real objective or goal so there really isn't a whole lot to do. Of course removing the movement controls from the player kind of eliminated an entire aspect of the game. Things are kind of slow going as I do not spend an incredible amount of time working on this project. I probably have too many at the moment which is why I do not have more updates. But if I can kind of get some semblance of a game going we might be talking more frequent updates. 

Other mentions

Its subtle but noticed I have changed the title too. The gameplay is starting to develop a little more clearly in my head. Time will tell where it goes. But the name of the game is now 'Frontiersman' the game idea might be a bit obvious. You are controlling a family starting out in a new world trying to survive and discovering the dangers that lurk in your new world.  

Roadmap updates

  • Terrain
    • finish tile-type transitions
    • add dirt (with transitions)
    • add gravel (with transitions)
    • add random stones
  • Player controls new
    • map movement controls new
    • designating actions for map items new
      • chop/down tree new
  • AI Simulated Character
    • add basic decision-based model
    • add crappy path-finding method
    • add hunger, starvation, and death
    • add actions and event, thoughts and memory
  • Save/Load
    • Test, test, test
  • Build Scripts and release checklist

Monday, August 29, 2016

Green Algae: Game Development Update


It's been a while since I have posted updates on one of my old game projects. It has been slow going. I was particularly blocked on building a save file format. Finally decided to implement saving and loading via the remarkably light minimal-json library. I also had to take the time to convert the project to gradle so it was easy to pull in the libraries auto-magically. Also realigned the trees into the each particular tile and adjusted the number of logs spawned after chopping one down although the math is not working very well. I get either 2 logs or no logs for smaller trees. That needs some tweaking.


I still have not decided what style of game It will be. I've only been really working on small insignificant details at this point. As you can see an incomplete update of smooth transitions between tile types which should be finished soon enough. I've been toying with the idea of moving more towards a Dwarf Fortress / RimWorld type of game. My map generation algorithm will need to become more sophisticated over time. I have been working on a few ideas to create a more versatile and generic system so that different types of terrain are possible. But first getting the terrain transitions to be generic and easily definable is probably necessary.

I have removed a little annoying gameplay element where by chopping down a tree required that you continuously collided with the tree by moving into it. This sort of mechanism was a bit confusing when not knowing you had to collide with it. Adjustments to log pickup will probably benefit from not having to be moving while colliding with the log hit box. Although these types of adjustments are secondary to figuring out which direction the game will take.

I am definitely open to ideas and/or suggestions even cries for a released version for anyone who still reads this blog. I've only really been working on the code for years now mostly a bit of a pass-time effort slowly but steadily trying to move it forward to a playable version.

Apparently the bridge building mechanic was broken with a few updates to map and world objects as part of building a save/load feature. But that could probably be fixed, though a quick mechanic test world would be cool since the map generation is not that quick to run, especially on my old laptop since it's only a dual-core.

But please feel free to leave your comments concerns etc. It'd definitely be nice to know if anyone is interested since it's really just a personal pet project at this point. Though I feel pet projects are where some of the most in-depth games come from.

Short-Term Roadmap

  • Terrain
    • finish tile-type transitions
    • add dirt
    • add gravel
    • add random stones
  • AI Simulated Character
    • add basic decision-based model
    • add crappy path-finding method
    • add hunger, starvation, and death
    • add actions and event, thoughts and memory
  • Save/Load
    • Test, test, test
  • Build Scripts and release checklist
That should be more than enough to focus on in the short-term. It might take a bit of doing to refactor the code to convert from a character based movement scheme to one of an overview and direction based one. We'll just take it step by step and see what happens.

Another idea I've been toying with is cutting the size of the tiles in half going from 32x32 pixels to 16x16 still keeping the base image resolution at 32x32 but simply scaling to half the size. Which might significantly break things but would be flexible after fixing.

Anyway that's it for this update. Just needed to write down some thoughts and try to create some semblance of interest as well as a place to hold myself accountable for plans.

Tuesday, May 24, 2016

Game optimization by space partitioning: Part II

Reduce rendering calls

Note that last time we reduced the number of objects returned in collision detection using a bin-ing strategy from 10020 to just around 31 objects. But then after profiling the application we noticed that the most time was now being spent in the rendering loop. Upon examination both loops were largely inefficient they were in fact both performing loops on 10020+ objects each call which was happening at both 33fps and the updates were as often as possible. 

Since the strategy existed already it was easy enough to figure out how a bounding box of objects to grab each time we render the screen and only render those objects since they are the only ones that are visible.

One problem that arose from this was the fact that the way the views work the actual objects on screen were significantly scaled.

Handle scaling

Screen size was 640x480 but each tile is 8x8 and is scaled. Blown up by a factor of 5. So grabbing a 640x480 section of from the SpacePartitionStrategy resulted in returning over 5000 objects.

If we take the inverse scale factor for the x and y directions which where 1/5 since each x and y was multiplied by 5. Then we get a grid size of 128x96 so instead of about 80*60 (4800) objects we now are only rendering 16*12 or 192 objects approximately. Of course it comes out to more like 200 or so objects based on bin boundaries and that will fluctuate when we add in smooth scrolling on maps.

The savings are incredible and give many many more benefits for future development.

 Check out the commits

You can check out the diffs of the four commits created for these two posts.

Abstract partitioning scheme                  32994afbc7d8bf2c34f4e3246473acb9eace8d7f
Space partitioning  that does not work   4e09bed3aff2f03856ff282ec4c6e1d91ca6ed58
Fix integer bin partition strategy             e62a1760dd9c59d6d8619b88f03a24f573c23e37
Reduce Rendering using Partitioning      fb896ef2098972b6007bb1cb0b03d74e14f93ce6

Friday, May 20, 2016

Game optimization by space partitioning

But first, a recap of LD#35

I participated in the last ludumdare competition. I love to participate in the competitions, they are an incredible challenge which forces me to focus and learn about how unprepared I am. Also how few public code I've actually released. Most of my entries I have started from scratch and each time I get a little bit farther than I did before, but still way behind where I need to be in order to actually make a game during the competition.

I tend to dive into writing a lot of boilerplate code that would already be written for me in an engine though I've never really found an engine I like. Though I am contemplating going back to SDL one of the few graphics libraries that actually provided all the necessary drudge work to write a game on top of. Otherwise I will stick with writing a game for ludumdare with the code from my last entry.

Pup8Bit an engine

So yeah I did not create a game I only created an engine and not the perfect one at that. It had a couple of bugs. Including no transparent images which was a huge time sync during the competition. Silly Java. Besides needing to make transparent images work, there was a huge issue with collision detection where the character movement code actually was checking it's current position instead of checking the next position for validity. But now that is working correctly.

Did some refactoring of the main Game object to off load all event handlers, updaters and rendering queues to game state objects.

Oh and this may be a little odd and out there but during the competition I added javascript support for scripting. Then quickly added coffeescript support after that. This uses Javas "Nashorn" javascript engine.  And grabbed the javascript distribution from the github repo.

Long story short with that, I intend to use the coffeescript files in a resources/states directory as init scripts for game states so all your objects can be added to the game state via coffeescript. This will allow me to reload the game states and watch the file system for changes to the scripts automatically restarting the state if the script changes. There is already a game initialization script that is loaded right now and does all the keyboard input handling for the current test game.

Ok, the problem - Performance Profiling

So the project is moving along, I have already resolved a couple of major performance bottlenecks with the code, as in somebody (me) was generating new transformation matricies in GameView everytime an object was rendered. Obviously this caused some major gc issues. But that has been resolved storing the transformations efficiently. But there are still occasional pauses when moving about the screen. Using jvisualvm helped catch the last performance issue so lets see if it helps in this circumstance.

So most of the time is being spent in the GamePosition.isClose method. Though there really isn't much to optimize there which is, maybe in getBounds call which does instantiate a new bounding box when there isn't one already but that should not take up too much time after the first call.

Heres the code for isClose.

  public boolean isClose(Renderable r) {
    return distSq(r.getPosition()) < (r.getBounds().getRadiusSq() * 10d);
  public double distSq(GamePosition update) {
    double dx = (getX() - update.getX());
    double dy = (getY() - update.getY());
    return dx * dx + dy * dy;

Really not much we can do about optimizing the calculations like my previous post indicated through experimentation. So really we need to go a step above that to the either the GameState.isClose or the GameState.neighbors method.

isClose just purely asks an individual position if a renderable object is close to it

private boolean isClose(Renderable r, GamePosition update) {
return update.isClose(r);

So nothing we can do to optimize that except eliminate the function call. Definitely not our concerning code.

And then here we have it. Where all of our time is being spent.

public Renderable[] neighbors(GenericGameObject go, GamePosition update) {
Set nearbys = new HashSet(); for (Set rSet : byLayer.values()) { for (Renderable r : rSet) {
if (isClose(r, go.getPosition()) && r != go) {
return nearbys.toArray(new Renderable[nearbys.size()]);

So pretty ugly here we are going through each layer and checking every renderable object to see if its close to the position we care about. Oh and all the while doing a bunch of memory allocations in to boot.

What we need is to reduce the overall number of checks. Yes we could pass back a reference to the hashset or store a field for the hashset and reuse that clearing it every update cycle etc. Or some such non-sense but as long as the number of items that we are iterating over is small there isn't really anything wrong with this code. So we shouldn't try to do crazy abnormal optimizations in order to eliminate the memory allocation. I think our biggest way to identify why this is a problem set of code is to output how many renderables get iterated over in this check.

So I added in some code to found how many Renderables in the inner loop were called.

And got a whole bunch of the following

Iterating over 10020
Iterating over 10020
Iterating over 10020
Iterating over 10020

This is for a small map from Tiled. So the app then performs fairly well for doing all those iterations every update on top of rendering at 33fps. But we are kind of wasting vast amounts of cycles here.

We need those extra cycles for doing input handling, AI logic, handling particle movement, etc, etc. So lets get them back shall we.


Ok so how about we drop the byLayers and just have a separate collection for all 10020 objects. Then what if instead of just one collection how about we use small collections of objects that are close together position wise. I mean this is mostly a filtering out unlikely candidates to get to a small number of objects that significantly reduces the impact of the loops.

A lot of people like to suggest quad trees or other data structures. I on the other hand like to use a grid based partitioning scheme where lookup time is constant time and aggregation is O(n) where n is the number of objects in the area of space we are grabbing. Though on the flip side a quad tree would give you O(log n) lookup time where n is the number nodes in the quad tree you have to traverse but then there is no aggregation time if each node has a list of objects in that section of the tree. Otherwise you have to continue traversing and still build a collection. I might eventually implement a combined method using bins of a certain size but each bin is a quad tree and the quad tree has nodes that contain the entire list of objects in that space. Removal time might be a problem though so might need to keep non-static objects out of it.

Defining the space partitions

We will say out space partitions are 4 tiles wide by 4 tiles high. Can go in any direction and the spacial grid starts at 0,0 and goes to MAX_INTEGER/2, MAX_INTEGER/2 only positive values. We want to be able to add renderable objects to the partition strategy. And get all objects within any bounds, regardless of layer. We want to allow for negative positioned renderable objects so we'll put renderables centered at MAX_INTEGER/4, MAX_INTEGER/4 in our grid system. We will also want our code to handle any bin size. So we can optimize for our bins. Obviously with a quad tree system our bins would only be allowed to contain a maximum number of elements thereby helping make iterations and performance more constant. With bins though the bins can have any number of objects in them so it would be based solely on how many objects occupy that space. Good for top-down rpgs where the maps are pretty static and there are not going to get very busy in one section of the maps. RTS' might benefit from quad tree with an implementation that reduces insertion time an keep back-references to the node an objects in for updating purposes.

Game types to use with bins

  • Turn-based Strategy
  • Top-down RPG
  • Simulation Games
  • 2D Shooters are ok
  • Platformer
I think all of the above should perform fine with binning as a space partition strategy.

Ok now it's time for....


This ends up being our bin calculation.
private int getBin(int x, int y) {
return BIN_OFFSET + (y * BIN_COLUMNS + x);
We calculate the bin by taking a base number BIN_OFFSET adding the number of elements for the beginning of the row in the grid we are currently in so y * BIN_COLUMNS where columns are the number of columns in our grid. I actually made the size of the bin grid just the square root of the BIN_OFFSET
// just make the number of possible bins really large
private static final int BIN_OFFSET = Integer.MAX_VALUE / 4;
private static final int BIN_COLUMNS = (int) Math.sqrt(BIN_OFFSET);
This is still pretty large for game maps. It's 23170 elements.

Benefits of Space Partitioning

So here we go now what are the benefits of this strategy. Before we were iterating over "Iterating over 10020" each update loop

Now we are

Iterating over 31
Iterating over 31
Iterating over 31
Iterating over 31
Iterating over 31

So wow we dropped 9989 iterations. 

Check Profiling

Now lets check the profiling to see if there is anything else we can optimize.

Looks like a lot of time is now spent in rendering. And that reminds me that we were looking at only the collision detection code and not the rendering code due to the most significant time user.

We could easily now use the abstract SpacePartitionStrategy and the methods on it to reduce the number of rendering calls the application is making every render which is now the most significant path.

I will let you know those benefits next time.

Sunday, May 15, 2016

Quick distance checking!


A while ago (ah hem 8 years ago) I made a post about how to implement basic bounding box coliision detection. I thought I would make a post about how to use a little short-cut method to determine if two objects are nearby each other.

The Problem

If we have a world full of objects, which are anything from the trees, and grass to the little particles racing around the screen we do not want to needlessly check every object with every other object if we do not have to. For instance, an object on the left side of the screen could not possibly collide with an object on the right side of the screen.

You want to eliminate as many of these expensive mathematical calculations as possible. Or perhaps you just want to see if two objects will affect each other anytime soon. There are a couple things we need to know about the objects in order to quickly make the determination if we want to check them. We might be currently checking collisions on objects that will never touch each other. Each time we can eliminate a future check it is can save us from wasting a check. Although not as big of a problem with modern day graphics if you use the GPU for rendering. Still it will help update cycles which that we run on the CPU and anything that is still prone to bottlenecks.

There may also be other areas where you want to quickly find all objects close or nearby each other. I plan to cover some partitioning strategies in the future that will help eliminate massive amounts of loops from being necessary.

The Math

We want to determine if two objects are close to each other. We need to at least have a radius around the objects in order to calculate whether or not they are within another objects radius. So we use the distance between the two objects which is calculated as

// SquareRootCalculator
double d = Math.sqrt( Math.pow(object1.x - object2.x, 2) + Math.pow(object1.y - object2.y,2));

We can improve the speed of this a little bit by short-cutting the math and applying some variables.

// SingleDiffCalculator
double diffX = object1.x - object2.x;
double diffY = object1.y - object2.y;
double distSquared = diffX * diffX + diffY * diffY;

No Math routine calls and eliminate the need to calculate difference twice. Although the compiler and JIT may not use a register for diffX and diffY they may instead decide to use the stack which is less optimal but probably negligent difference in performance. You can expand it out to be a long equation.

// DirectFromObjectsCalculator
double distSquared = (object1.x - object2.x) * (object1.x - object2.x) + (object1.y - object2.y) * (object1.y - object2.y);

And because I like to take things farther than they need to be here accessing the x and y variables may not be efficient enough since the objects were probably allocated on the heap and may not be in cpu cache lets force them to be put on the stack which is probably in cache still.

// DirectFromStackCalculator
double ox1 = object1.x;
double oy1 = object1.y;
double ox2 = object2.x;
double oy2 = object2.y;
double distSquared = (ox1-ox2) * (ox1-ox2) + (oy1-oy2) * (oy1-oy2);

Because I like to be thorough lets see if that matters at all lets put them into a utility class and use a Unit Test and get some output. And lets do it in an object oriented way.

Ok so there was not much of a difference or enough to be noticable between methods.

283 ms for 10000000 using DirectFromObjectsCalculator
263 ms for 10000000 using DirectFromStackCalculator
283 ms for 10000000 using SingleDiffCalculator
268 ms for 10000000 using MathCalculator
304 ms for 10000000 using SquareRootCalculator

Another run:

336 ms for 12000000 using DirectFromObjectsCalculator
347 ms for 12000000 using DirectFromStackCalculator
391 ms for 12000000 using SingleDiffCalculator
394 ms for 12000000 using MathCalculator
409 ms for 12000000 using SquareRootCalculator

These results did not change much on repeated runs and varied a bit between winners the only obvious looser was the SquareRootCalculator obviously.

So no need to go drastically changing your coding style use variables if you want to clean things up. Doing temporary calculations like the SingleDiffCalculator.

If you would like to fiddle with the code then you can find it here.

The Check

So the final piece which I should have mentioned before going into all that testing above, is the comparison of against the radius.

The calculation returns the squared distance so we need to see if the square of the distance from the objects centers is less than the square of the sum of the radii.

Something like

double radiusSquared = Math.pow(object1.radius + object2.radius, 2);
if(distSquared < radiusSquared) {
  // objects could be colliding
  // objects not colliding

That should be about it. Hopefully I will get some time to back fill that repo with examples from earlier snippets I posted.

Saturday, March 26, 2016

Dungeon Crawler in Java

I have begun building a dungeon crawler game. The premise of the game that I came up with is a little odd for a dungeon crawler but hopefully it will be interesting and you'll like it.

So the world is going to be made up of dungeons, yeah obviously. The dungeons will have been created from a simulation of AI dwarves starting from just two in a random area. I plan on creating some unique monsters that spawn in order to slow or stop the dwarves quest to build meaningful dungeons. Build in some magical items and of course hopefully some humorous history generated for NPCs, books, spells, and items in the dungeon crawl.

The world currently is all dirt except for a 5x5 area of grass where the dwarves will start out, need to add in minerals and rare metals etc. Also little hazards ;)

Tools I'm using:

Heres a snippet from the Dwarves current behaviortree

    public static AICreature createMaleDwarf(final World world) {
        InOrderSequence root = new InOrderSequence<>();
        SelectorNode isHealthy = new SelectorNode<>();
        SelectorNode isDanger = new SelectorNode<>();
        isDanger.addChild(context -> {
            return world.findHostiles(context, context.getAwarenessDistance()).length > 0;
        }, isHealthy);
        Action attack = context -> {
            return NodeStatus.FAILURE;
        isHealthy.addChild(context -> {
            return context.getHealth() > 80;
        }, new LeafNode(attack));

        LeafNode isBored = new LeafNode<>(context -> {
            if (world.every(context, 0.3)) {
            return NodeStatus.RUNNING;

        return new Dwarf(root,;


Thursday, March 10, 2016

JRuby for game development

So I have been pretty active in using Ruby for the past several years. I have found it a great resource for writing less code and producing more results. So why not use it for game development. Build some DSLs or better syntax for writing game logic code. So in this post I am going to run through a couple of ways to accomplish writing a game in ruby by using java for graphics and additional functionality.

So first we start off by needing to package everything up nicely in a single jar file so it appears as though we're just using java. Unfortunately this comes with a bit of a space cost. And that space is that of jruby the complete jar is ~20mb you can find them at so no way to avoid this although you can do something like write an install script that downloads it and then puts your source into it afterwards.

Ok once you have the jar file you will add your code to it and it will become your executable from java.

Make a copy of the complete jar.

$ cp jruby-complete- mygame.jar

Create a file that jruby will launch called jar-bootstrap.rb

#!/usr/bin/env ruby
puts "Hello, I am jar-bootstrap.rb from inside the jar file"

Update the jar (-u) by first modifying the manifest to run a specific java class using option -e to override the Main-Class entry in the manifest already inside the jar.

$ jar ufe mygame.jar org.jruby.JarBootstrapMain

Then you can use the -u option to add files to the jar file or update existing ones.

$ jar uf mygame.jar jar-bootstrap.rb

Then viola:

 $ java -jar mygame.jar
Hello, I am jar-bootstrap.rb from inside the jar file.

Ok we've entered the ruby~java land woot woot.

Now for lets rubify java to do our game-logics bidding!!!

Lets switch the jar-bootstrap.rb to load our game which we will start in a game.rb file:

jar-boostrap.rb becomes
#!/usr/bin/env ruby
require './game.rb'

Then we make our game.rb file with a simple example of loading a java swing window and rendering loop

game.rb is
#!/usr/bin/env ruby
include Java

import javax.swing.JFrame
import javax.swing.JPanel
import java.awt.BorderLayout
import java.awt.Dimension

class MyDrawPane < JPanel
  def initialize
    setDoubleBuffered true

  def paintComponent(g)
    g = g.create
    g.drawString 'Hello from ruby', 0, self.height / 2

class MyGame < JFrame

  def initialize
    super "My Game Window Title"

    self.setDefaultCloseOperation JFrame::EXIT_ON_CLOSE
    self.setLocationRelativeTo nil
    self.setVisible true


And with all this we have a simple window to start from but now we can use the power of ruby to rule the world. Uh I mean we'll use the power of ruby to make games... rule the world...

So this is all great but maybe we want easier iterations with our game development because updating the jar all the time isn't that fast. So for development just execute your game.rb file from jruby directly. You can use the original one you downloaded.

$ java -jar ../jruby-complete- game.rb

Or if you use rvm or rbenv then just execute the game script. And Q.E.D.