Paul's picture

Plankton has gotten really close to figuring out how to make a crabby patty. But no matter how hard he tries, he still can't figure out the ingredients for that bread + lettuce + tomato + patty sandwich.

So how did Block Story succeed where Plankton failed? How does the game know that when you combine certain items in some order and quantity you get the crabby patty?

The problem

You have a grid 2x2 or 3x3 (or any arbitrary grid size for that matter). You have potentially hundreds of recipes, each one with 1 to 9 items in any quantity. For example:

 
       Bread       
  Patty  
  Bread  

V

Crabby Patty

When the user enters ingredients, the goal is to recognize that his ingredients match one of the recipes and can produce some output.

Notice we would like to make it so that if the ingredients are in the first, second or last column, it still matches.

We would also like to make it so that if the user puts 10 of each ingreadients,  it still matches,  produces 1 crabby patty, and then he is left with 9 of each ingredients. 

Another thing to watch out for:  it could be possible to have more than 1 recipe matching the user input. So the recipes should be designed carefuly so that they are never ambiguous  

Brute force

The naive approach, would be:  every time the table changes contents,  look at each recipe and see if it matches.  Notice if you have say 500 recipes,  this could actually take some time.  There also remains the issue of dealing with alignment problems (having the ingredients in any column). Checking one by one would require comparing each recipe and for each recipe, comparing all cells,  so its performance is O(n*s) where n is the amount of recipes, and s is the size of the grid.

If you think this is a reasonable approach. Then what the heck are you doing building a block engine? just quit right now and come back in a few years.

Solving the Alignment problem

The alignment problem is easy to solve. When reading a recipe,  only store columns and rows that have something,  throw away all empty columns and rows. For example, Plankton would only have to remember this:

 

 
Bread
Patty
Bread

V

Crabby Patty
 

 

 

Meaning,  he only has to remember that 1 column with bread, patty and bread produces a crabby patty, and forget that this is for 3x3 or 10x10 grid.

When matching the user input, he can do the same process: eliminate all empty columns and rows. So if the user enters any one of these:

 
Bread         
Patty    
Bread        
 
       Bread       
  Patty  
  Bread  
 
              Bread
    Patty
    Bread

The result will be exactly the same:

 

 
Bread
Patty
Bread

 

Now we compare the results with the recipes.  This solves the alignment problem for all recipes regardless of grid size. But I have still not touched on making it efficient.

Matching recipes efficiently

I don't do it exactly like this, but this is a convenient way to explain the algorithm.  For both the recipe and the user input,  you can encode it as a string,  like this:

 
Bread
Patty
Bread
 
1x3BPB

Which means the recipe is 1 column by 3 rows, and it has from left to right top to bottom Bread, Patty and Bread.

You can build an entire table from these strings with all the recipes.  For example:

Encoded ingredients Output Description
1x3BPB 1 crabby patty 1 column 3 rows recipe for crabby patty
1x1R 3 red dyes just 1 cell with 1 ruby ore produces 3 red ores
3x3WWWW_WWWW 1 chest

1 rows with 3 wood,
1 row with 1 wood empty and wood,
1 row with wood produces a chest

...    

Now, when the user puts something in the crafting table,  encode what he enters into a string using the same algorithm,  and then it is just a matter of looking up the string in this table.

The simplest way to do this, is to store that table in a Dictionary or Hash table, then the lookup can be done in O(1), meaning it does not matter how many recipes there are.

So the algorithm is:

  1. At game startup,
    1. eliminate all empty rows and columns from all recipes
    2. encode each recipe into a string
    3. put all encoded recipes into a hash table indexed by the encoded string
  2. When the user puts something in the crafting table
    1. eliminate all empty rows and columns from the input
    2. encode the result into a string
    3. lookup that string in the recipe hash table
    4. if matches, then show the output for that recipe

At game startup, the algorithm performs O(n*s) which is fine because it is done only once while the user enjoys our cool loading screen.

When the user enters something, the algorithm does the matching in O(s) where s is the size of the grid.

 

Hmmmm? I'm not following you

Hmmmm? I'm not following you on this???

check out GREENLINE's site! a game me and my team have recently started. our site will show you it In it's early stage. we will be adding to the site soon.

It is part of the "block

It is part of the "block engine demystified" series, where I explain how to do some of the things.

It is mostly useful for other devs crazy enough to attempt to develop this.

I love this series...

I like to know how things work.

I learned the practical side of this the hard way back in September of last year - knew there had to be a reason behind the behavior i was seeing.

All of these file compression type techniques that you're using to reduce size and increase speed are certainly a paradigm shift when you think about the bloatware of MS.

I haven't written a recipe in months, but there is some recent interest in this topic of late, isn't there.

Thanks again for an informative article.

singlespeed retrogrouch

Good manners don't cost nothing now do they - Pink Floyd

Oh so not for me lol

Oh so not for me lol

check out GREENLINE's site! a game me and my team have recently started. our site will show you it In it's early stage. we will be adding to the site soon.

well now i can tell plankton

well now i can tell plankton how to make the crabby patty Tongue

also, if you read closely, part of this will be helpful if you are trying to make cheat recipes that would actually make sense and not a goofy recipe

£ {[(< Awesoman >}]) £

Infinity: https://infinity.cm/Awesoman
Facebook: https://www.facebook.com/AlphaAwesoman
Google+: https://plus.google.com/+AlphaAwesoman
Twitter: @Alpha_Awesoman

I am one with Ashkore! Bomb

wait a minute...

So are we getting Crabby Patties in the next update or what?

Giggles Defence Squad Leader

I am the pike.

i dont think so

paul was showing this as an example

£ {[(< Awesoman >}]) £

Infinity: https://infinity.cm/Awesoman
Facebook: https://www.facebook.com/AlphaAwesoman
Google+: https://plus.google.com/+AlphaAwesoman
Twitter: @Alpha_Awesoman

I am one with Ashkore! Bomb

Pikeman

He isnt talking literally. Its metaphorical. Basically hes giving a vague explanation of how that part or the game works to anyone interested in attempting to do something similar.

On another note, paul if you would give such an explanation for how the radar works, it would help me out on my own game Im creating Winking

Tyng again

I posted a comment saying I wasjoking, but it doesnt seem to be there anymore. Pensive

Giggles Defence Squad Leader

I am the pike.

:O

That was complex. Surprised my retarded brain figured it out. Laughing

I may be low ranked, but im still a Mewtwo!!

Circle of Life

Hello Paul,
I've been playing Blockstory for a little while, but only recently start taking a look at the webpage/forum. Recently, I read your technical blogs, being a coder I found very interest, thank you. In section "The circle of life" you state if we want you to elaborate into a section to ask you. Well, I'm curious about "generate". Since this takes the longest to run, does most of the "work". I guess it is a good chunk of code. So, I'll try and make my questions specific. I curious how the seed affects generation. Like why is "flattyflatflat" (according to description is flat - I havent taken a look, yet) when it really shouldn't have any effect based on words in the seed, is it just a fluke?
This isnt directly related, but a quest spawned by it. In the radar system, does it scan the full 32x32x32 area or just a section of the area? If its scanning the the array for "bio blocks" (spawners, people, etc), couldnt there be a radar for mineral blocks?

Thank for your time and effort on the game and in the forums.
- Gman

-Gman
Warrior Poet
The Boss of Naughty Thing

Sorry, for bumping this but I

Sorry, for bumping this but I realy am interested in what Paul as to say about my above questions.

-Gman
Warrior Poet
The Boss of Naughty Thing

Other people have requested

Other people have requested more information about this particular topic.

I could write books about procedural terrain generation Happy, but I will try to write some intro material in just a few blog posts

Thank you, Paul. I apprecaite

Thank you, Paul. I apprecaite the response (I know I'm not floating in limbo).
I've been debating back and forth to ask this... but here it goes. I would love to even review the code (willing to sign an NDA, I have no plans for a 3D world) but I totally understand if its too propriatary and at the core of your I.P. So, a rejection won't hurt my feelings, I'll totally understand. Also, if you just don't want to have to deal with a bunch of other people making such a request I would get that too. Thank you.

-Gman
The Boss of Naughty Things

-Gman
Warrior Poet
The Boss of Naughty Thing

Check the next article,

Check the next article, hopefully it begins to shed some light about this part.

You should check minepackage or techcraft that are open source if you want to see some source code.

Thank you, Paul. I appreciate

Thank you, Paul. I appreciate the direction.

-Gman
Warrior Poet
The Boss of Naughty Thing