[Guide] Fill algorithm

Tako · Before February 2015

Hey. I made a fill algorithm. I hope a couple of you will find it interesting. I know I did. It's kind of interesting to watch.

It works by randomly spreading out from one point and then stopping when it reaches a boundary, or rather, anything that is not the replaceId. If you want to remove the cool growing effect, you can just add them all to a list, shuffle, and build them all afterward instead of building them as it goes.

Specifically, it...
• selects start block
and then...
• adds blocks on all sides that aren't already filled or outside of bounds
• adds the blocks to a list
• selects a random point
• removes it from list
• repeats until the list is empty

It might seem like it's slowing down, but it's actually running at the same speed the entire time. It just has a larger border to fill and can't do it as fast as when it was small.

You can also fill over extra blocks by replacing `map[x, y, 0].Id == replaceId` with `replaceIds.Contains(map[x, y, z].Id)`, where replaceIds is a List<int> of the ids you want to ignore.

Pastebin if you like the syntax highlighting: http://pastebin.com/htSeAXtQ (not updated)

        // Start x, start y, the ID that it will be filled with, the ID that it will replace.         // The layer is automatically detected, but if you set it then it won't change it.         private static void Fill(int x, int y, int fillId, int replaceId, int layer = 0)         {             List<Point> points = new List<Point>(); // Point is from System.Drawing & lets you remember x's/y's.             Block[, ,] map = r.Map;                 // replace with whatever method you use to read the map.                                                     //   It needs to contain all the blocks in the room.                                                     //   I use a three-dimensional array of Block objects.                                                     //   Blocks are found by typing Map[x,y,layer].              // If the layer has been set, use it. Otherwise, automatically detect. (Only set             layer = layer != 0 ? layer : replaceId >= 500 ? 1 : 0;              do // using a do-while instead of a while because the list starts at 0 and it wouldn't execute.             {                 // if you're on the replace id, replace it and remove it from the list.                 if (map[x, y, layer].Id == replaceId)                 {                     Build(fillId, x, y);                      map[x, y, layer] = new Block(fillId, x, y);                      points.RemoveAll(s => s.X == x && s.Y == y);                 }                 else // If you're not on the replace id, you're on the border. Select a random point and remove it from the list.                 {                     var RanPoint = points[Tools.Ran.Next(points.Count)]; // Do not use `new Random` here. Do it outside the loop.                      x = RanPoint.X;                      y = RanPoint.Y;                      for (int ind = 0; ind < points.Count; ind++)                         if (points[ind].X == x && points[ind].Y == y)                             points.RemoveAt(ind);                 }                  // Where there is replaceId, draw and add a point. Update the map and it becomes exponentially faster.                 UpdatePoint(x + 1, y, fillId, replaceId, ref map, ref points);                 UpdatePoint(x - 1, y, fillId, replaceId, ref map, ref points);                 UpdatePoint(x, y + 1, fillId, replaceId, ref map, ref points);                 UpdatePoint(x, y - 1, fillId, replaceId, ref map, ref points);                  // You just added a few points to the list, generally 2-3.                 // Return, select a random one, delete it, and repeat until there are none left.                 // What you end up with in the List<Point> points is all the points that have not been checked, aka the ones on the front line.             } while (points.Count > 0); // Once the list is empty, it is done.         } // end Fill function          private static void UpdatePoint(int x, int y, int fillId, int replaceId, ref Block[, ,] map, ref List<Point> points)         {             if (map[x, y, layer].Id == replaceId)             {                 b.Push.Build(fillId, x, y);                  map[x, y, layer] = new Block(fillId, x, y);                  points.Add(new Point(x, y));             }         }

[Edit] Changed `out` to `ref`, fixed id mismatch (used `id` instead of `fillId`)
[Edit2] Used LINQ instead of for loop.
[Edit3] Added layer support.

Last edited by Tako (Jul 30 2014 10:59:59 am)

hummerz5 · Before February 2015

props for the cupid shuffle references.

I did this once. It worked... then it stopped working. yay bugs!

Though, this looks slightly more sophisticated.

TiKen · Before February 2015

Pseudo-recursive algorithm. Ahhhh, dream of my childhood!

But I don't get why you did this like this... points contains points that have already been replaced (see UpdatePoint). So why bother checking every time?

ugotpwned · Before February 2015

Well, I've noticed a bug while looking through your code, if it even matters to you.

for (int ind = 0; ind < points.Count; ind++) if (points[ind].X == x && points[ind].Y == y)     points.RemoveAt(ind);

This doesn't work because if it were to remove a point from the list all the objects's indicies get moved - 1. An easy fix is just to enumerate backwards through the list.

Last edited by UgotPwned (Jul 30 2014 1:18:58 am)

Tako · Before February 2015

UgotPwned wrote:

Well, I've noticed a bug while looking through your code, if it even matters to you.
for (int ind = 0; ind < points.Count; ind++) if (points[ind].X == x && points[ind].Y == y)     points.RemoveAt(ind);
This doesn't work because if it were to remove a point from the list all the objects's indicies get moved - 1. An easy fix is just to enumerate backwards through the list.

Not quite. For loops check the boolean after every iteration. When it checks, it gets a fresh value of points.Count.

I use this exact code in my own program, and have tested it several times. If it threw an exception I would've fixed it by now.

ugotpwned · Before February 2015

Tako wrote:

For loops check the boolean after every iteration. When it checks, it gets a fresh value of points.Count.

No, the problem is not the for loop condition, it's when an array or list has two or three elements in a a row that would be removed with RemoveAt, this causes the failure becuase after shifting all the elements to the left, it essentially skips an element. And I can prove it.

List<int> myInts = new List<int>(); myInts.Add(2); myInts.Add(1); myInts.Add(2); myInts.Add(3); myInts.Add(2); myInts.Add(2); myInts.Add(2); myInts.Add(4); myInts.Add(2);  for (int i = 0; i < myInts.Count; i++) {       if (myInts[i] == 2)       {            myInts.RemoveAt(i);       } }

Go ahead and unit test that. It's not going to throw an exception, but at the end of the loop, myInts contains a two.

Last edited by UgotPwned (Jul 30 2014 10:39:48 am)

Tako · Before February 2015

So you could also solve the problem by doing `i--;` after you remove, correct? That seems more intuitive than going backwards, even though they both fix the problem.

ugotpwned · Before February 2015

Tako wrote:

So you could also solve the problem by doing `i--;` after you remove, correct? That seems more intuitive than going backwards, even though they both fix the problem.

Yeah that's another way you could fix it.

Last edited by UgotPwned (Jul 30 2014 11:31:29 am)

Processor · Before February 2015

Wtf? Why not LINQ?

points.RemoveAll(s => s.X == x && s.Y == y);

Anch · Before February 2015

Is this code to put into your bot? Because I wanted to make a bot that fills stuff...
I bet I sound stupid. Right?

Tako · Before February 2015

anch159 wrote:

Is this code to put into your bot? Because I wanted to make a bot that fills stuff...

Yes.

I bet I sound stupid. Right?

Kinda. You're in Bots and Programming.

Official Everybody Edits Forums

#1 Before February 2015

[Guide] Fill algorithm

#2 Before February 2015

Re: [Guide] Fill algorithm

#3 Before February 2015

Re: [Guide] Fill algorithm

#4 Before February 2015

Re: [Guide] Fill algorithm

#5 Before February 2015

Re: [Guide] Fill algorithm

#6 Before February 2015

Re: [Guide] Fill algorithm

#7 Before February 2015

Re: [Guide] Fill algorithm

#8 Before February 2015

Re: [Guide] Fill algorithm

#9 Before February 2015

Re: [Guide] Fill algorithm

#10 Before February 2015

Re: [Guide] Fill algorithm

#11 Before February 2015

Re: [Guide] Fill algorithm

Board footer