- prva cast prepisu kodu pre pozuivanie space_t a space_t API, ktore je optimalizovany pre ukladanie informacii o

objektoch vo velkych mapach.
POZOR: nie je vhodne kompilovat ako gameserver ( pre istotu to ani nejde ) // este to msusim doorbit :)




git-svn-id: http://opensvn.csie.org/tuxanci_ng@63 0ee4d065-81f0-4d1e-b06c-ff20ad07cc3e

1 files changed, 370 insertions, 0 deletions

diff --git a/src/space.c b/src/space.c
new file mode 100644
index 0000000..ce662f0
--- /dev/null
+++ b/src/space.c
@@ -0,0 +1,370 @@
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include "main.h"
+#include "list.h"
+#include "space.h"
+
+#ifdef DEBUG_SPACE
+
+typedef struct recv_struct
+{
+	int id;
+	int x, y;
+	int w, h;
+} recv_t;
+
+recv_t* newRecv(int x , int y, int w, int h)
+{
+	static int last_id = 0;
+
+	recv_t *new;
+
+	new = malloc( sizeof(recv_t) );
+	memset(new, 0, sizeof(recv_t));
+
+	new->id = ++last_id;
+	new->x = x;
+	new->y = y;
+	new->w = w;
+	new->h = h;
+
+	return new;
+}
+
+void getStatus(void *p, int *id, int *x, int *y, int *w, int *h)
+{
+	recv_t *recv;
+
+	recv = p;
+
+	*id = recv->id;
+	*x = recv->x;
+	*y = recv->y;
+	*w = recv->w;
+	*h = recv->h;
+}
+
+void setStatus(void *p, int x, int y, int w, int h)
+{
+	recv_t *recv;
+
+	recv = p;
+
+	recv->x = x;
+	recv->y = y;
+	recv->w = w;
+	recv->h = h;
+	recv->x = x;
+}
+
+void destroyRecv(recv_t *p)
+{
+	free(p);
+}
+
+#endif
+
+static int my_conflictSpace(int x1,int y1,int w1,int h1,int x2,int y2,int w2,int h2)
+{
+	return (x1<x2+w2 && x2<x1+w1 && y1<y2+h2 && y2<y1+h1);
+}
+
+space_t *newSpace(int w, int h, int segW, int segH,
+		  void (*getStatus)(void *p, int *id, int *x, int *y, int *w, int *h),
+		  void (*setStatus)(void *p, int x, int y, int w, int h))
+{
+	space_t *new;
+	int i, j;
+
+	new = malloc( sizeof(space_t) );
+	memset(new, 0, sizeof(space_t));
+
+	new->w = w / segW + 1;
+	new->h = h / segH + 1;
+	new->segW = segW;
+	new->segH = segH;
+	new->getStatus = getStatus;
+	new->setStatus = setStatus;
+	new->list = newList();
+
+	new->area = malloc( new->w * sizeof(list_t **) );
+
+	for( i = 0 ; i < new->w ; i++ )
+	{
+		new->area[i] = malloc( new->h * sizeof(list_t *) );
+	}
+
+	for( i = 0 ; i < new->h ; i++ )
+	{
+		for( j = 0 ; j < new->w ; j++ )
+		{
+			new->area[j][i] = newList();
+		}
+	}
+
+	return new;
+}
+
+static void getSegment(space_t *p, int x, int y, int w, int h,
+		       int *segX, int *segY, int *segW, int *segH)
+{
+	*segX = x / p->segW;
+	*segY = y / p->segH;
+	*segW = ( (x+w) / p->segW + 1 ) - *segX;
+	*segH = ( (y+h) / p->segH + 1 ) - *segY;
+}
+
+void addObjectToSpace(space_t *p, void *item)
+{
+	int segX, segY, segW, segH;
+	int id, x, y, w, h;
+	int i, j;
+
+	p->getStatus(item, &id, &x, &y, &w, &h);
+	getSegment(p, x, y, w, h, &segX, &segY, &segW, &segH);
+
+	for( i = segY ; i < segY + segH ; i++ )
+	{
+		for( j = segX ; j < segX + segW ; j++ )
+		{
+			addList(p->area[j][i], item);
+		}
+	}
+
+	addList(p->list, item);
+}
+
+void getObjectFromSpace(space_t *p, int x, int y, int w, int h, list_t *list)
+{
+	int segX, segY, segW, segH;
+	int id, this_x, this_y, this_w, this_h;
+	int i, j, k;
+
+	getSegment(p, x, y, w, h, &segX, &segY, &segW, &segH);
+
+	for( i = segY ; i < segY + segH ; i++ )
+	{
+		for( j = segX ; j < segX + segW ; j++ )
+		{
+			void *this;
+
+			for( k = 0 ; k < p->area[j][i]->count ; k++ )
+			{
+				this = p->area[j][i]->list[k];
+				p->getStatus(this, &id, &this_x, &this_y, &this_w, &this_h);
+
+				if( my_conflictSpace(x, y, w, h, this_x, this_y, this_w, this_h) &&
+				     searchListItem(list, this) == -1 )
+				{
+					addList(list, this);
+				}
+			}
+		}
+	}
+}
+
+void* getObjectFromSpaceWithID(space_t *p, int id)
+{
+	int this_id, x, y, w, h;
+	void *this;
+	int i;
+
+	for( i = 0 ; i < p->list->count ; i++ )
+	{
+		this  = p->list->list[i];
+		assert( this != NULL );
+
+		p->getStatus(this, &this_id, &x, &y, &w, &h);
+
+		if( this_id == id )
+		{
+			return this;
+		}
+	}
+
+	return NULL;
+}
+
+int isConflictWithObjectFromSpace(space_t *p, int x, int y, int w, int h)
+{
+	int segX, segY, segW, segH;
+	int id, this_x, this_y, this_w, this_h;
+	int i, j, k;
+
+	getSegment(p, x, y, w, h, &segX, &segY, &segW, &segH);
+
+	for( i = segY ; i < segY + segH ; i++ )
+	{
+		for( j = segX ; j < segX + segW ; j++ )
+		{
+			void *this;
+
+			for( k = 0 ; k < p->area[j][i]->count ; k++ )
+			{
+				this = p->area[j][i]->list[k];
+				p->getStatus(this, &id, &this_x, &this_y, &this_w, &this_h);
+
+				if( my_conflictSpace(x, y, w, h, this_x, this_y, this_w, this_h) )
+				{
+					return 1;
+				}
+			}
+		}
+	}
+
+	return 0;
+}
+
+void delObjectFromSpace(space_t *p, void *item)
+{
+	int segX, segY, segW, segH;
+	int id, x, y, w, h;
+	int index;
+	int i, j;
+
+	p->getStatus(item, &id, &x, &y, &w, &h);
+	getSegment(p, x, y, w, h, &segX, &segY, &segW, &segH);
+
+	for( i = segY ; i < segY + segH ; i++ )
+	{
+		for( j = segX ; j < segX + segW ; j++ )
+		{
+			index = searchListItem(p->area[j][i], item);
+			assert( index != -1 );
+			delList(p->area[j][i], index);
+		}
+	}
+
+	index = searchListItem(p->list, item);
+	assert( index != -1 );
+	delList(p->list, index);
+}
+
+void delObjectFromSpaceWithMem(space_t *p, void *item, void *f)
+{
+	void (*fce)(void *param);
+
+	fce = f;
+
+	delObjectFromSpace(p, item);
+	fce(item);
+}
+
+void moveObjectInSpace(space_t *p, void *item, int move_x, int move_y)
+{
+	int old_segX, old_segY, old_segW, old_segH;
+	int new_segX, new_segY, new_segW, new_segH;
+	int id, x, y, w, h;
+
+	p->getStatus(item, &id, &x, &y, &w, &h);
+	getSegment(p, x, y, w, h, &old_segX, &old_segY, &old_segW, &old_segH);
+	getSegment(p, move_x, move_y, w, h, &new_segX, &new_segY, &new_segW, &new_segH);
+/*
+	printf("%d %d %d %d  -> %d %d %d %d \n",
+		old_segX, old_segY, old_segW, old_segH,
+		new_segX, new_segY, new_segW, new_segH);
+*/
+	if( old_segX != new_segX || old_segY != new_segY ||
+	    old_segW != new_segW || old_segH != new_segH )
+	{
+		delObjectFromSpace(p, item);
+		p->setStatus(item, move_x, move_y, w, h);
+		addObjectToSpace(p, item);
+		return;
+	}
+
+	p->setStatus(item, move_x, move_y, w, h);
+}
+
+void printSpace(space_t *p)
+{
+	int i, j;
+
+	printf("print space : \n");
+
+	for( i = 0 ; i < p->h ; i++ )
+	{
+		for( j = 0 ; j < p->w ; j++ )
+		{
+			printf("%3d ", p->area[j][i]->count);
+		}
+
+		putchar('\n');
+	}
+}
+
+void destroySpace(space_t *p, void *f)
+{
+	void (*fce)(void *param);
+	int j, i;
+
+	fce = f;
+
+	//getObjectFromSpace(p, 0, 0, p->w * p->segW - 1 ,  p->h * p->segH - 1, list);
+
+	destroyListItem(p->list, fce);
+
+	for( i = 0 ; i < p->h ; i++ )
+	{
+		for( j = 0 ; j < p->w ; j++ )
+		{
+			destroyList(p->area[j][i]);
+		}
+	}
+
+	for( i = 0 ; i < p->w ; i++ )
+	{
+		free(p->area[i]);
+	}
+
+	free(p->area);
+	free(p);
+}
+
+#ifdef DEBUG_SPACE
+
+void test_space()
+{
+	space_t *space;
+	list_t *list;
+	int i, j;
+	
+	space = newSpace(5000, 2500, 320, 240, getStatus, setStatus);
+
+	for( i = 1 ; i < 16 ; i++ )
+		for( j = 1 ; j < 16 ; j++ )
+		{
+			recv_t *this;
+
+			this = newRecv(j*160, i*120, 32, 32);
+			//addToSpace(space, newRecv(j*550, i*550, 1, 1) );
+			addObjectToSpace(space, this );
+			delObjectFromSpaceWithMem(space, this, destroyRecv);
+		}
+
+	list = newList();
+	getObjectFromSpace(space, 640, 480, 800 , 600, list);
+
+	printf("list->count = %d\n", list->count);
+
+	for( i = 0 ; i < list->count ; i++ )
+	{
+		recv_t *recv;
+		recv = list->list[i];
+
+		printf("%3d %3d %3d %3d\n", recv->x, recv->y, recv->w, recv->h);
+	}
+
+	destroyList(list);
+
+	printSpace(space);
+
+	destroySpace(space, destroyRecv);
+}
+
+#endif
+