How to make a fill bucket in paint?

[tonyssheep]

I'm trying to make a fill bucket for my paint program. Python says it reached max depth of recursion. I know what that mean. My question is: Am I on the right track at least? Or this doesn't even make any sense? How am i suppose to do it?

[DemonWasp]

Your problem looks like this:

1. Suppose we start at (50,50) and our area is (1024,768) in size.

2. We mark (0,0) as new color and recurse into (49,50).

3. We mark (49,50) as new color and recurse into (48,50).

4. Repeat pattern from (2) and (3) about fifty times.

5. We can't go left (x-1) anymore, and going right (x+1) goes back to a point where we've already been. Instead, we take the next option, and go up (y-1). We mark (0,49) as new color.

6. Aha, but now we can go right, so we recurse into (1,49).

7. Repeat step 6 about 1024 times.

Our stack depth is now well over 1000 frames, and we've only just started.

What you want to do is keep track of points to be visited in a queue. When you visit a point, do:
- add that point to the visited set, or mark that point as visited somehow
- add all unvisited (not in visited set) neighbours of that point to the queue

After visiting each point, pull the next one off the stack. No recursion required.

[tonyssheep]

I tried making it with a list. I tried a few different methods. This is the only one that seems like it should work. What's wrong with it?

By the way, how do I post my codes here in this text box instead of adding an attachment? If I just copy and paste here. All indents and colours are gone.

[DemonWasp]

Post your code between either [ code ] [ / code ] tags, or [ syntax = "Language" ] [ / syntax] tags (minus the spaces). I don't know whether compsci.ca supports syntax highlighting for Python yet, but it never hurts to try (it will default back to looking like a Code block labeled "Python" if it isn't supported).

I don't speak Python fluently, so I'm not sure, but I think your biggest problem has to do with making things more complicated than they need to be. I've written the algorithm below, but I'll try to walk you through how it matches up to my previous recommendation:

DemonWasp @ Wed Jan 11, 2012 10:44 am wrote:

What you want to do is keep track of points to be visited in a queue. When you visit a point, do:
- add that point to the visited set, or mark that point as visited somehow
- add all unvisited (not in visited set) neighbours of that point to the queue

After visiting each point, pull the next one off the stack. No recursion required.

I haven't tested this code at all (don't have Python on my work computer), and as previously stated, I'm not particularly familiar with the language. Still:

Python:

# We will need a queue for "points to visit" and a set for "points already visited" from collections import deque from sets import Set def flood ( x, y, newClr, oldClr ):         # See: http://docs.python.org/tutorial/datastructures.html         # We add our first point to examine, which is our starting location.         visit_queue = deque ( [(x,y)] );                 # Haven't visited anything yet: start with an empty set         visited = Set()                 # Represent your neighbourhood this way; it makes it easier to deal with.         # Later on, if you want to move to 8 points (or more), change this list.         neighbourhood = [ (-1,0), (+1,0), (0,-1), (0,+1) ]                 # While there are still points left to visit         while visit_queue:                 # Get the next point to visit                 pt = visit_queue.popleft()                                 # If that point is not the border color, and we haven't visited it                 if screen.get_at(pt) != oldClr and pt not in visited:                         # Change the colour                         screen.set_at(pt, newClr)                                                 # Mark this point as visited (add that point to the visited set)                         visited.add(pt)                                         # Identify neighbours and add them to the to-be-visited list.                         for n in neighbourhood:                                 visit_queue.append ( ( pt[0] + n[0], pt[1] + n[1] ) ) # Your main-line stuff here...

[tonyssheep]

I tried to read your method. What I got is this: I think you've created a loop that never ends because it keeps on checking (pt[0]-1,pt[1]+0) because visit_queue.popleft() only returns the left point. Here's what I did. I can see I'm falling in to mass number of cases again. Would you please tell me what's wrong with mine or yours?

[DemonWasp]

The popleft() method will remove the first element of the list and return it. The code you've written to grab all the elements out of the deque and into a list (pt) is unnecessary complication. Your code will also add the neighbourhoods of points which were NOT supposed to be coloured (such as points we have already visited and points which have the "border color", oldClr).

You may also want to check that the parameters you're giving to flood() match the ones you're sending to draw.circle(). The colour you draw the circle in is bright green, and the flood call will fill in bright red, and will only stop at black (0,0,0). This probably isn't what you intended.


I think the problem with my code is that I never check against the boundaries. That is, I never discard points outside [ (0,0), (width,height) ). This means that my code will happily fill out to infinity.

The if statement should be modified to check that the point is actually on the screen. You should only have to modify one line to add this check. It may help if you add a method to check whether a single point is on the screen.


For debugging purposes, I recommend:
1) Resize your screen to something very small; you might want to start at 5 x 1 and work up from there.
2) Each time you pop a new point, print out its coordinates. You should only be visiting each point once, so if you see duplicates, you know something is up.
3) Comment your code as you write it, to make your intentions absolutely clear. This will help me determine whether your code does what you meant for it to do.

[tonyssheep]

Thank you so much!!!!! It worked.
So what am I suppose to do here. Make you the correct answer or something? How do I end this problem.

[DemonWasp]

Just say thanks. We don't really "end" threads here (maybe we should, it's definitely open for discussion).

[Aange10]

There definitely should be some sort of reflection at the end of posts. Ties in sorta with a discussion we had before about finding posts and reading through them for 20 minutes to find out they are useless.