Login
User Name:

Password:



Register
Forgot your password?
Vote for Us!
auth_update crash
Dec 23, 2017, 10:15 pm
By Remcon
check_tumble
Dec 18, 2017, 7:21 pm
By Remcon
parse description bug
Dec 15, 2017, 10:08 pm
By Remcon
Couple bugs
Dec 12, 2017, 5:42 pm
By Remcon
Bug in disarm( )
Nov 12, 2017, 6:54 pm
By GatewaySysop
LoP 1.46
Author: Remcon
Submitted by: Remcon
LOP 1.45
Author: Remcon
Submitted by: Remcon
LOP Heroes Edition
Author: Vladaar
Submitted by: Vladaar
Heroes sound extras
Author: Vladaar
Submitted by: Vladaar
6Dragons 4.3
Author: Vladaar
Submitted by: Vladaar
Users Online
CommonCrawl, Yandex, DotBot

Members: 0
Guests: 4
Stats
Files
Topics
Posts
Members
Newest Member
478
3,708
19,242
612
Jacki72H
Today's Birthdays
There are no member birthdays today.
Related Links
» SmaugMuds.org » General » Smaug Snippets » Floodfill algorithm
Forum Rules | Mark all | Recent Posts

Floodfill algorithm
< Newer Topic :: Older Topic > Better floodfill

Pages:<< prev 1 next >>
Post is unread #1 Jun 28, 2006, 9:10 am
Go to the top of the page
Go to the bottom of the page

mordecai

GroupMembers
Posts99
JoinedNov 17, 2005

On both the overland snippet, and afkmud a horribly inefficient algorithm is used to floodfill - which not only lags, but causes crashes when trying to fill large areas.

I have completely recoded the floodfill algorithm along with it's friend undo. Anyone interested in the code?
       
Post is unread #2 Jun 28, 2006, 6:13 pm
Go to the top of the page
Go to the bottom of the page

Sanami

GroupMembers
Posts3
JoinedApr 25, 2004

sure
       
Post is unread #3 Jun 28, 2006, 8:41 pm
Go to the top of the page
Go to the bottom of the page

Samson
Black Hand
GroupAdministrators
Posts3,639
JoinedJan 1, 2002

Sure. Always open to more efficient and improved code.
       
Post is unread #4 Jun 29, 2006, 8:35 am   Last edited Jul 7, 2006, 9:06 am by mordecai
Go to the top of the page
Go to the bottom of the page

mordecai

GroupMembers
Posts99
JoinedNov 17, 2005

Replace all the floodfill junk in overland.c with the following: (this includes the undo functions and data structure defines)
#ifdef MAPEDIT_UNDO
/* Stuff for the floodfill and undo functions - greatly enhanced by Mordecai */
struct undo_data
{
	int value[MAX_X*MAX_Y];
	int size;
	
	short map;
	short prevterr;
} undo_data;
bool pop_undo(int *x, int *y)
{
	if(undo_data.size > 0) {
		int p=undo_data.value[--undo_data.size];
		*x=p/MAX_Y;
		*y=p%MAX_Y;
		return TRUE;
	}
	return FALSE;
}    
bool push_undo(int x, int y)
{
	if(undo_data.size < MAX_X*MAX_Y -1) {
		undo_data.value[undo_data.size++]=MAX_Y*x+y;
		return TRUE;
	}
	return FALSE;
}
#endif

bool pop_fill(FILL_STACK *stack, int *x, int *y)
{
	if(stack->size > 0) {
		int p=stack->value[--stack->size];
		*x=p/MAX_Y;
		*y=p%MAX_Y;
		return TRUE;
	}
	return FALSE;
}    
bool push_fill(FILL_STACK *stack, int x, int y)
{
	if(stack->size < STACK_SIZE -1) {
		stack->value[stack->size++]=MAX_Y*x+y;
		return TRUE;
	}
	return FALSE;
}
/* superior floodfilling - Mordecai */
short floodfill(short map, int x, int y, short fill, char terr) {
	FILL_STACK stack;
	int ycoord1;
	bool spanLeft, spanRight;
	
	stack.size=0;
	if (terr == fill)
		return 1;

	if (!push_fill(&stack, x, y))
		return 2;

	while (pop_fill(&stack, &x, &y)) {
		ycoord1 = y;
		while (get_terrain( map, x, ycoord1 ) == terr && ycoord1 >= 0)
			ycoord1--;
		ycoord1++;
		spanLeft = spanRight = FALSE;
		while (get_terrain( map, x, ycoord1 ) == terr && ycoord1 < MAX_Y) {
#ifdef MAPEDIT_UNDO
			push_undo(x,ycoord1);
#endif
			putterr( map, x, ycoord1, fill );
			if (!spanLeft && x > 0 && get_terrain( map, x - 1, ycoord1 ) == terr) {
				if (!push_fill(&stack, x - 1, ycoord1))
					return 2;
				spanLeft = 1;
			} else if (spanLeft && x > 0
					&& get_terrain( map, x - 1, ycoord1 ) != terr) {
				spanLeft = 0;
			}
			if (!spanRight && x < MAX_X - 1
					&& get_terrain( map, x + 1, ycoord1 ) == terr) {
				if (!push_fill(&stack, x + 1, ycoord1))
					return 2;
				spanRight = 1;
			} else if (spanRight && x < MAX_X - 1
					&& get_terrain( map, x + 1, ycoord1 ) != terr) {
				spanRight = 0;
			}
			ycoord1++;
		}
	}
	return 0;
}

#ifdef MAPEDIT_UNDO
short unfloodfill( void )
{
	char terr;
	int i, x, y, p;
	
	//nothing to undo
	if(undo_data.size<=0) return 1;
	
	terr = get_terrain( undo_data.map, undo_data.value[0]/MAX_Y, undo_data.value[0]%MAX_Y );
	for( i=undo_data.size-1; i>=0; i-- ) { //let's not pop, that way we can undo the undo
		p=undo_data.value[i];
		x=p/MAX_Y;
		y=p%MAX_Y;
		putterr( undo_data.map, x, y, undo_data.prevterr );
	}
	undo_data.prevterr = terr;
	
	return 0;
}

void new_undo(short map, char terr) {
	undo_data.map=map;
	undo_data.prevterr=terr;
	undo_data.size=0;
}
#endif

In do_mapedit find:
      send_to_char( "Usage: mapedit undo\r\n", ch );

Replace with:
#ifdef MAPEDIT_UNDO
      send_to_char( "Usage: mapedit undo\r\n", ch );
#endif


Replace:
      new_undo( ch->map, standingon );

With:
#ifdef MAPEDIT_UNDO
      new_undo( ch->map, standingon );
#endif


Replace:
   if( !str_cmp( arg1, "undo" ) )
   {
      short undo = unfloodfill(  );

	//don't remember what's exactly in here, I think it was ifchecks instead of a switch, and no
	//third error case like me
   }

With:
#ifdef MAPEDIT_UNDO
   if( !str_cmp( arg1, "undo" ) )
   {
      short undo = unfloodfill(  );

		switch( undo ) {
		case 0:
			display_map( ch );
			send_to_char( "&RUndo successful.\r\n", ch );
			return;
		case 1:
			display_map( ch );
			send_to_char( "&RNothing to undo!\r\n", ch );
			return;
		default:
			send_to_char( "Unknown error during undo.\r\n", ch );
			return;
		}
   }
#endif

Finally at the end of do_mapedit find:
#ifdef MAPEDIT_UNDO
   send_to_char( "Usage: mapedit undo\r\n", ch );
#endif

Replace with:
#ifdef MAPEDIT_UNDO
   send_to_char( "Usage: mapedit undo\r\n", ch );
#endif



In overland.h find:
#define OVERLANDCODE /* Interaction with other snippets */

And add immediately after:
/* Uncomment this if you want undo capabilities */
#define MAPEDIT_UNDO


Then find:
/* Adjust these to fit the size of the maps you want for your world */
#define MAX_X 1000
#define MAX_Y 1000

And add this immediately after:
/*
 * This is the size of the stack for the floodfill algorithm.
 * Really only needs to be the size of MAX_X, since it pushes
 * something only for each verticle line.
 */
#define STACK_SIZE 5000

Find:
typedef struct mapreset_data MAPRESET_DATA;

And add immediately after:
typedef struct fill_stack FILL_STACK; //floodfill algorithm

Find:
struct sect_color_type
{
   short sector;  /* Terrain sector */
   char *color;   /* Color to display as */
   char *symbol;  /* Symbol you see for the sector */
   char *desc; /* Description of sector type */
   bool canpass;  /* Impassable terrain */
   int move;   /* Movement loss */
   short graph1;  /* Color numbers for graphic conversion */
   short graph2;
   short graph3;
};

Add immediately after:
//for floodfill algorithm
struct fill_stack {
	int value[STACK_SIZE];
	short size;
};

Find:
void fix_maps( CHAR_DATA * ch, CHAR_DATA * victim );
short get_terrain( short map, short x, short y );

Add immediately after:
//floodfill algorithm
bool pop_fill(FILL_STACK *stack, int *x, int *y);
bool push_fill(FILL_STACK *stack, int x, int y);
void empty_fill(FILL_STACK *stack);


That should do it. If I missed something, tell me and I'll include it :P. Also, there might have been leftover structures and definitions in overland.h that you should remove that is associated with the old undo.

The reason I have a define to include undoing is because it takes up a good sum of memory, so it might not be everyone's cup of tea (lots of memory for minor functionality). If someone has an idea of how to reduce the memory for that, that would be greater. Otherwise, I must point out that I changed it because allocating tons of small blocks of memory on the fly is VERY slow - converting to the new undo structure increased the speed by three times (pretty much as fast as without undo).

NOTE: This is the vertical stripe floodfill algorithm - pretty much the fastest in existence. By using a stack instead of recursion, greater efficiency is gained, while assuring no stack overflow. Also, by doing the fill in vertical stripes, there is less stack management overhead, increasing performance even more (and memory for the stack).

June 29 UPDATE: Had a minor bug that's fixed in the code now. Undo couldn't undo itself before.
July 7 UPDATE: Undo twice would sometimes not work because I was incorrectly handling array indexes (index 0 was never used).
       
Post is unread #5 Jun 29, 2006, 8:42 am
Go to the top of the page
Go to the bottom of the page

mordecai

GroupMembers
Posts99
JoinedNov 17, 2005

One more thing, if you include this in AFKmud and the snippet, if you could add me as a contributor that would be great :). Also keeping my comments intact would be nice, but I'm not going to be a Nazi about it.
       
Post is unread #6 Jul 1, 2006, 9:48 am
Go to the top of the page
Go to the bottom of the page

mordecai

GroupMembers
Posts99
JoinedNov 17, 2005

Just curious if anyone's attempted to implement this.
       
Pages:<< prev 1 next >>