fill point maximum Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 02-17-2004, 09:46 PM Many of you know how "filling" an area with a certain color works. As some of you may also know, this is how the simplest pathfinding (search) works, too. Now, the algorithm in question starts from one single point and moves out until there is nothing left to fill. From that point, 4 (or 8) points around it are checked, and then the points around them are checked, and so on. Call the points-to-be-checked the "fill points": any algorithm stores those fill points for the next iteration. The challenge is to figure out a precise equation for a fill point maximum, given that the 2D array is of size xmax and ymax. Assume that the fill progresses in 4 directions: N, S, E, W. (or 8 directions, or both combinations, if you're up to it) The "block points" would be any points that stop the progression of fill points. On the map, "block points" can be in any combination. The fill point maximum comes from one particular arrangement of block points so that there is a maximum of fill points active at one time. Here are two possible scenarios: (extremes) 1) No block points. Fill point maximum for that arrangement is: (x ^ 2 + y ^ 2) * 4 (the fill pattern progresses in a diamond shape) 2) Maze configuration. Assume that the maze looks like this: Code:```|=====| |     | | |=| | |   | | |===| |       | ======|``` Thus, this gives a fill point maximum of 2. Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 02-18-2004, 05:02 AM * Has anyone read this? * Does anyone think this is a worthy challenge? * Is anyone in pain because of trying to solve this? Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. broan496 Junior Member Posts: 35 Threads: 5 Joined: May 2003 02-18-2004, 05:11 AM I've read it but it is way out of my league but good luck. PlayGGY Member Posts: 144 Threads: 8 Joined: Feb 2004 02-21-2004, 11:21 AM I don't quite get what you are asking, especially the stuff abaout "fill point maximum". When filling a region, the "brute force" method you mentioned is just about the slowest method possible. To fill a convex polygon (all angles are < 180), just find the verticies, and then it is very simple to fill using a simple equation. To fill a concave is harder. KiZ Posting Freak Posts: 2,771 Threads: 96 Joined: Oct 2003 02-21-2004, 05:56 PM Quote:* Is anyone in pain because of trying to solve this? Er... Kinda? My brain is in pain attempting to understand your challenge. Either I cant understand it, or all that fill point maximum stuff is way beyond me. =D Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 02-21-2004, 07:19 PM Quote:I don't quite get what you are asking, especially the stuff abaout "fill point maximum". When filling a region, the "brute force" method you mentioned is just about the slowest method possible. To fill a convex polygon (all angles are < 180), just find the verticies, and then it is very simple to fill using a simple equation. To fill a concave is harder. That's not how you do it at all. I'm not talking about simple mathematical shapes here. I'm talking about a 2D array where the block points (ie: where the fill does not progress) can be anywhere, even randomly dispersed. Quote:Er... Kinda? My brain is in pain attempting to understand your challenge. Either I cant understand it, or all that fill point maximum stuff is way beyond me. =D To understand the fill point maximum, first you have to understand how the fill works. Then what a fill point is. Then what a fill point maximum is.. Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. Antoni Gual Posting Freak Posts: 1,407 Threads: 117 Joined: Dec 2002 02-22-2004, 02:14 AM If you are challenging us to do a fill function i have one ready. If you are challenging us to calculate that fill point maximum thing you should elaborate. Most of us have no idea about what it is. If you are just showing us how clever you are, well .... Antoni Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 02-22-2004, 02:22 AM Quote:If you are challenging us to calculate that fill point maximum thing you should elaborate. Most of us have no idea about what it is. Do you know what I'm talking about? Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. PlayGGY Member Posts: 144 Threads: 8 Joined: Feb 2004 02-22-2004, 07:31 AM So, it is a 2D array? Why not just loop through it and test each element...? I must not understand what you are asking... Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 02-22-2004, 08:12 PM Quote:So, it is a 2D array? Why not just loop through it and test each element...? Because the fill starts with one point, and proceeds to surrounding, non-block points until there are no points left to fill. Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. « Next Oldest | Next Newest »