I'm working on a game where you can draw and color pictures. The coloring part basically works as a 2d-array with quadrants of a picture. These quadrants can be either empty, unvisited or visited. I need an algorithm that would find a path for automatic coloring, which would look at least somewhat natural. I've been trying to do this for some time, but so far I haven't been able to make it look nice.
An example of a 2d-array of a picture (a simple circle in this case, but there are more complex shapes and even a multitude of shapes in an array which are not connected) with [o] being the empty quadrants and [-] being the unvisited quadrants.
[o][o][o][o][o][o][o][-][-][o][o][o][o][o][o][o]
[o][o][o][o][-][-][-][-][-][-][-][-][o][o][o][o]
[o][o][o][-][-][-][-][-][-][-][-][-][-][o][o][o]
[o][o][-][-][-][-][-][-][-][-][-][-][-][-][o][o]
[o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
[o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
[o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
[o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
[o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
[o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
[o][o][-][-][-][-][-][-][-][-][-][-][-][-][o][o]
[o][o][o][-][-][-][-][-][-][-][-][-][-][o][o][o]
[o][o][o][o][-][-][-][-][-][-][-][-][o][o][o][o]
[o][o][o][o][o][o][o][-][-][o][o][o][o][o][o][o]
The current system works in the following way: I set the starting position and then get a list of quadrants that satisfy the conditions set by this "path finding" algorithm. Right now I'm just finding all the unvisited quadrants that are adjacent with an empty or visited quadrant and hoping that it would move around the edges and close in on the center. After getting the list I choose the closest quadrant to the current position and start moving towards it. When the current position gets close enough to the target, I update the list and find another closest quadrant and so on. The problem is that the coloring does not look natural because it is jittery. I guess the reason is that my conditions for finding these quadrants aren't clear enough, so when I'm picking the closest one it's actually not quite on the desired path.
public void UpdateAutoFill()
{
Vector2 pencilPos = Pencil.instance.gameObject.transform.position;
Vector2 targetPos = _quadrantNavigator.PositionShapesPos +
(Vector2)Pencil.instance.gameObject.transform.parent.position;
if (Vector2.Distance(pencilPos, targetPos) < targetDistanceToSwitch) //Get new target
{
if (!_quadrantNavigator.SetNextTargetAlt()) // No targets left
{
FinishStage();
return;
}
}
float adjSpeed = autoFillSpeed * (_quadrantNavigator.InitialQuadrantCount / 500f);
if (adjSpeed < 20)
adjSpeed += (20 - adjSpeed) / 1.5f;
Vector2 direction = targetPos - pencilPos;
Vector2 delta = adjSpeed * Time.deltaTime * direction.normalized;
if (delta.magnitude > direction.magnitude)
delta = direction;
Vector2 finalPos = pencilPos + delta;
Pencil.instance.rigidbody.MovePosition(finalPos);
}
public bool SetNextTargetAlt()
{
// Sets all quadrants on position and within radius for quadrants as visited
VisitCurrentPosition();
List<QuadrantPosition> quadrantsInDirection = GetQuadrantsOnEdge();
if (quadrantsInDirection.Count == 0) // No targets left at all
{
return false;
}
float minSqrDist = quadrantsInDirection.Min(quadPos => quadPos.SqrDistanceTo(_position));
_position = quadrantsInDirection.Where(quadPos => quadPos.SqrDistanceTo(_position) == minSqrDist).First().pos;
return true;
}
private List<QuadrantPosition> GetQuadrantsOnEdge()
{
return _unvisitedQuadrants.Where(quadPos =>
{
if (quadPos.quadrant != FillQuadrant.Unvisited)
return false;
return QuadrantIsOnEdge(quadPos);
}).ToList();
}
private bool QuadrantIsOnEdge(QuadrantPosition quadPos)
{
int offset = 1;
int row = quadPos.row;
int col = quadPos.col;
for (int i = row - offset; i <= row + offset; i++)
{
for (int j = col - offset; j <= col + offset; j++)
{
if (i >= _rows || i < 0 || j >= _cols || j < 0)
continue;
if (_quadrants[i, j] != FillQuadrant.Unvisited)
return true;
}
}
return false;
}
Let's say you already know the points to color, using the adequate algorithm. If you want to fill the geometry from one corner to another, you could use the Manhattan distance.
private void SortManhattan(List<Point> pPoints)
{
pPoints.Sort((p1, p2) =>
{
return p1.X + p1.Y - p2.X - p2.Y;
});
}
If you wish to fill from the edge of your geometry, and towards the center of your geometry, while rotating around the center, you could try something like this.
private void SortCirclingAroundCenter(List<Point> pPoints)
{
var centerX = (double)pPoints.Sum(p => p.X) / pPoints.Count;
var centerY = (double)pPoints.Sum(p => p.Y) / pPoints.Count;
pPoints.Sort((p1, p2) =>
{
var cc1 = new CircleCoordinate(centerX, centerY, p1);
var cc2 = new CircleCoordinate(centerX, centerY, p2);
return cc1.CompareTo(cc2);
});
}
Here is the CircleCoordinate class, it calculates a distance to the center and an angle. I didn't check it was working, it's only to give you a lead on what's possible to do;)
public class CircleCoordinate : IComparable<CircleCoordinate>
{
public double DistanceToCenter { get; set; }
public double Angle { get; set; }
public CircleCoordinate(double pCenterX, double pCenterY, Point pPoint)
{
this.DistanceToCenter = Math.Abs(pPoint.X - pCenterX) + Math.Abs(pPoint.Y - pCenterY);
this.Angle = Math.Atan((pPoint.Y - pCenterY) / (pPoint.X - pCenterX));
}
public int CompareTo(CircleCoordinate other)
{
if (this.Angle != other.Angle)
{
// we draw while rotating around the geometry center
return this.Angle.CompareTo(other.Angle);
}
else
{
// we start drawing at the edge, closing in at the geometry center
return other.DistanceToCenter.CompareTo(this.DistanceToCenter);
}
}
}