0

Take a look for this game: http://paper-io.com/

I am stucking at algorithm to find inside part after move from this game.

enter image description here

Look at my photo. The original land of player is red. Player movement is orange. The new land is green.

My problem is how to specify green part. I think after complete movement, It may have two parts to choose as green here (green part and the outside grid part).

Choose a start and find the wall to know which part is result waste time much.

Thank you for reading.

  • You can use the *floodfill* algorithm. – Willem Van Onsem Jun 26 '19 at 10:17
  • but how to know which is the part inside: green part or gray-grid-part ? One way to know is that part next to wall (may use **floodfill** for that) But it waste time much –  Jun 26 '19 at 10:47
  • Not sure but maybe count the number of right turns and number of left turns? (that way you can tell in which direction the circle was closed so you can tell it's inside). – Yonlif Jun 26 '19 at 11:34
  • Are you trying to find this area from the picture? Or what is your input data? Are you saying the area is not always green? – Nico Schertler Jun 26 '19 at 15:27
  • Please specify your criteria for wasting too much time. You've rejected tracing the wall (which eliminates the `crossing number` approach) and flood-fill from the edge (which is the most straightforward). It would also help to have a description of the game; an off-site link to the "play game" page is not helpful. Even better, simply remove that reference; game play is not the problem you're trying to solve. – Prune Jun 26 '19 at 16:59

2 Answers2

0

Flood fill starting at every point on the outer edges that is not red or orange.

Stop at red or orange squares.

That will give you the area that you are not going to fill in, so just fill in whatever is left over.

Having 100%ed paper.io several times, I can verify that this is equivalent to what it does.

You can also flood fill simultaneously from both sides of the new wall. If one fill finds the outer edge, then discard that one and keep the other. If one stops before finding the outer edge, then keep that one and discard the other.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
0

You asked for, let's say, raster algorithm but let's try to generalize this problem.

Let's assume that we always remember the circuit of occupied (red) area and store it in a graph which looks like like circular linked list. Each node has coordinates (x, y). So we have something like that:

  A2 -- A3 -- A4
 /             \
A1             A5
 \             /
  A7 -------- A6

At the same time we remember one point inside the starting area.

Each round in this game starts somewhere on the circuit, either on existing node or on new node between existing two, and ends when the intersection of the motion vector and circuit is detected. Those nodes are P and R. Whole route drawned int this round creates new part of the circuit. Motion vector is a step made by "head" in each tick of time.

Starting node P splits edge A3 - A4 into two edges A3 - P and P - A4 which are added to the graph. Edge A3 - A4 is removed from the graph.

Each step of the move adds next edge: P - B1, B1 - B2, ... Finaly we exchange edge A6 - A7 with A6 - R and R - A7.

After each round graph looks like:

                B1 -- B2 -- B3
               /             \
  A2 -- A3 -- P -- A4         B4
 /                  \         |
A1                  A5        |
 \                  /         B5
  A7 ------ R --- A6         /
             \              /
              B7 --------- B6

Now it's time to walk through the graph and collect visiting nodes into new circuit. This walk is described in a range of polygon union algorithms or here (step 3 & 4).

When we have a new circuit, we can draw it and floodfill starting in the remembered point.

kolejnik
  • 136
  • 5