koobas.hobune.stream
Check for closed circuit of pickups
Hello all, me and a few friends are experimenting with some possible game ideas. Our attempts at creating this mechanic have been close but unfortunately broken.
The gameplay takes place upon a grid full of pickups. The player can attain these pickups in any order they like. Once they have created a circuit of attained pickups (circuit shown as red line); the circuit of attained pickups and the ones contained within; are transformed into bonus pickups.
Currently, each pickup has an ID and knows the ID of the pickup N E S & W of itself. The history of which pickups the player attains and in which order is recorded. We are checking for a circuit when the players location has 2 or more neighboring attained pickups. Stepping back through the playerPosition history to check if they have done a full circuit and then using a flood fill algorithm.
This works most of the time, however if the player is to exit the area of the current circuit they are creating and then return somewhere else (see picture below): In this circumstance, the flood fill executes when the player hits the blue coloured pickup, before the actual circuit is complete.
Basically, my question is: can anyone give us a shove in the right direction for a better way of calculating if a full circuit has been completed. The circuit doesnt have to be a square or rectangle, can be a very odd shape ... as long as it has unattained pickups contained within.
Ive been searching for some kind of mathematical algorithm to use but so far we are stumped.
Does the order of pickups matter (same question: in the 2nd picture, should it pop after the entire path? Should the center pop if they grab all 16 edge pickups in random order?)
Can the edge pickups ever pop (if they grab the three around the lower corner, should it become bonus?)
You mention checking the player's history, and recording NESW directions. If they were in a 2D array, and order didn't matter, you could s$$anonymous$$l code from a GO game.
In the example above, all 16 would need to be obtained before the centre would pop. The order in which the player takes the pickups shouldnt matter. However the player does not need to do the full 5x5 grid. They could do a 3x3 and pop the remaining 1 inside. Will have a look at "Go" now.
Can they connect any place other then the end? For example, could they have gone "straight" from the blue marked object another row or two before turning right? Also can they reenter using a sphere that is already in use?
I would approach this problem from a behavioral point of view: Create objects, but don't control them. Instaed tell them what, when and how to do their job.
The way I understand your question is that a circuit is complete if there exists a list of spheres, which connect to eachother. Instead of doing a top-down control scheme, what you should do is let the spheres themselves determine if they are a part of a circuit. I propose the following (recursive) solution:
Every time a new spehere is picked up, it sends a message to all neighboring speheres that have already been picked up. These neighboring spheres send a similar message to all picked-up neighbors except the source of the message. Now, if any sphere that has already sent a message receives one, it means it is a part of a circuit. The circuit could then be recovered by backtracking or other means if need be.
The message need not be an actual message, as you probably figured, a simple boolean flag that is set whenever the message sending function is called should suffice. Of course you might need something more complex if you have different types of spheres or circuits that cannot connect with eachother.
Also depending on how you want the actual search to behave, have a look at Depth First Search and Breadth First Search
You pretty much have it. After each pickup, select any unused space and do your flood fill. If that touches no edges, you're surrounded. At first, that will fill the entire area. But after enough pickups, the first flood fill will be cut off from other free squares. So, keep picking unfilled squares and flood-filling from there.
A sneaky way to say "run flood fill until done" is to have a loop going through all pickups (a nested loop if you use a 2D array, but sounds like you aren't?) Whenever it finds a free square, run floodfill on that square. All runs in O(n).
