Flowfield implemetation

icuurd12b42 · 2011-09-06 02:57:31

So, working on avoidance, a while back we had this challenge if you remember...

I started working on this FlowField dll. I got the idea from there and from this video

Anyway, before I got any further, I would like you guys to test out the early implementation...
http://www.host-a.net/u/icuurd12b42/FlowField.zip

Run the gmk in GM in debug to see how many instances you can have (hit space to add 100)

I need some ideas on the basic features. Right now I only have the basic field create, delete, create from bmp and a simple data fetching system to get the values and to calculate the vector/slope. It should support 3d fields, right now I only use one layer (a 2d grid) made of chars

The implementation was written rather quickly. If anyone can look at the source here, I forgot to ad in the zip:
(sorry for the ancient style of windows programming)

Expand// dllmain.cpp : Defines the entry point for the DLL application.
#include "stdafx.h"
#define WIN32_LEAN_AND_MEAN
#define NOGDI
//#include "stdafx.h" //when in msvc, not needed unless compiler complains
//#include "dll.h" //devc++, not needed
#include <windows.h>
#include <windowsx.h>
#include <stdio.h>
#define gmexport extern "C" __declspec (dllexport)

#define max(a,b)            (((a) > (b)) ? (a) : (b))
#define min(a,b)            (((a) < (b)) ? (a) : (b))
#define median(a,b,c)       (max(a,min(b,c)))

DWORD file_bin_read_byte(FILE* hf)
{
    return (DWORD)(int) getc(hf);
}
DWORD fileBinReadWord(FILE* hf, int count)
{
    //count specifies the number of bytes to form up the word
    DWORD ret; ret = 0;
    DWORD shift; shift = 0;
    for(int i = 0; i < count; i++)
    {
        ret+=file_bin_read_byte(hf) <<shift;
        shift+=8;
    }
    return ret;
}




BOOL WINAPI DllMain(HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpvReserved)
{
    switch (fdwReason)
    {
        case DLL_PROCESS_ATTACH:
            // attach to process
            // return FALSE to fail DLL load
            break;

        case DLL_PROCESS_DETACH:
            // detach from process
            break;

        case DLL_THREAD_ATTACH:
            // attach to thread
            break;

        case DLL_THREAD_DETACH:
            // detach from thread
            break;
    }
    return TRUE; // succesful
}

//The 3d char array
//consists of d number of planes, each plane is a layer alocated on a w*h (rectangle area) basiz
//imagine a number of 2d planes layers on top of each other
//this is done to be more memory friendly
//I could have alocated a cube instead but
//that is rather hard on the system
struct Arr3d
{
    int w; //width
    int h; //height
    int d; //depth (layers)
    int allocated; //num planes alocated, if we fail to alocate, this is used to free up to the last alocated layer
    DWORD planes[1]; //all the layers in an arry form
};

//Tell the c++ compiler to switch to standard C compiling so exported function names as not mangled
extern "C" {

//frees a field (3d array)
gmexport double GMFFDeleteField(double field)
{
    //get pointer
    Arr3d *arr = (Arr3d*) (DWORD)field;
    //not null
    if(arr == NULL) return (double)(DWORD) 0;
    
    //loop through layers alocated
    for(int i = 0; i<arr->allocated; i++)
    {
        //free the layer
        GlobalFreePtr((void*)arr->planes[i]);
        //next layer
        arr->allocated --;
    }
    //free structure
    GlobalFreePtr(arr);
    return (double)(DWORD)1;
}

//creates a field (3d array)
gmexport double GMFFAllocateField(double w, double h, double d)
{
    //alocate structure + all the pointers needed for the depth
    Arr3d *arr = (Arr3d*) GlobalAllocPtr(GMEM_ZEROINIT,sizeof(Arr3d) + sizeof(DWORD) * (DWORD)d);
    if(arr == NULL) return (double)(DWORD)NULL;
    //set basic properties
    arr->w = (int)(DWORD) w;
    arr->h = (int)(DWORD) w;
    arr->d = (int)(DWORD) d;
    arr->allocated = 0;
    
    //loop though the layers
    for(int i = 0; i<arr->d; i++)
    {
        //alocate the pointers
        arr->planes[i] = (DWORD) GlobalAllocPtr(GMEM_ZEROINIT,sizeof(char)*(arr->w*arr->h));
        if(arr->planes[i] == NULL)
        {
            //free the failed array
            GMFFDeleteField((double)(DWORD)arr);
            return (double)(DWORD)NULL;
        }
        //remember the aloc count. this is used when freeing, useful on freeing failed fully allocated array
        arr->allocated ++;
        
    }
    //return the field (array structure)
    return (double)(DWORD) arr;

}

//this creates a 2d area from a bitmap
gmexport double GMFFFieldFromBitmap(LPSTR bitmapfile)
{
/*
    readBMPFile
    Arguments:
        0 ds grid
        1 fname

    Returns:
        reads the 24 or 32 bit bmp image from fname and loads it's data in the ds grid

    resons for failure:
    File not found
    not a bmp file
    bmp is not 24bpp or 32bpp
    bmp is compressed
*/
	//attempt to open file
    FILE* file = fopen(bitmapfile, "rb");
    //failed
    if (file<=0)
    {
        return (double)(DWORD)NULL;

    }
    //is it BM?
    if(!((getc(file) == 'B') && (getc(file) == 'M')))
    {
        fclose(file);
        return (double)(DWORD)NULL;
    }
	//read the info
    DWORD fileSize; fileSize=fileBinReadWord(file,4);
    DWORD unused0; unused0=fileBinReadWord(file,2);
    DWORD unused1; unused1=fileBinReadWord(file,2);
    DWORD dataOffset; dataOffset=fileBinReadWord(file,4);
    DWORD headerBytes; headerBytes=fileBinReadWord(file,4);
    DWORD width; width=fileBinReadWord(file,4);
    DWORD height; height=fileBinReadWord(file,4);
    DWORD colorPlanes; colorPlanes=fileBinReadWord(file,2);
    DWORD bitsPerPixel; bitsPerPixel=fileBinReadWord(file,2);
    DWORD compression; compression=fileBinReadWord(file,4);
    DWORD dataSize; dataSize=fileBinReadWord(file,4);
    DWORD resolutionx; resolutionx=fileBinReadWord(file,4);
    DWORD resolutiony; resolutiony=fileBinReadWord(file,4);
    DWORD colorsInPalette; colorsInPalette=fileBinReadWord(file,4);
    DWORD importantColors; importantColors=fileBinReadWord(file,4);
    /*
    magicNumber BM
    fileSize 65590
    unused0 0
    unused1 0
    dataOffset 54
    headerBytes 40
    width 128
    height 128
    colorPlanes 1
    bitsPerPixel 32
    compression 0
    dataSize 65536
    resolutionx 0
    resolutiony 0
    colorsInPalette 0
    importantColors 0
    */
    //if not 24 or 32 bpp
    if((bitsPerPixel != 32) && (bitsPerPixel != 24))
    {
        fclose(file);
        return (double)(DWORD)NULL;
    }
    //if compressed
    if(compression != 0)
    {
        fclose(file);
        return (double)(DWORD)NULL;
    }
    //get the field
    Arr3d *arr = (Arr3d*)(DWORD)GMFFAllocateField(width, height, 1);
	//null
    if(arr==NULL)
    {
        fclose(file);
        return (double)(DWORD) NULL;
    }

    /*
    show_debug_message("magicNumber "+string(magicNumber))
    show_debug_message("fileSize "+string(fileSize))
    show_debug_message("unused0 "+string(unused0))
    show_debug_message("unused1 "+string(unused1))
    show_debug_message("dataOffset "+string(dataOffset))
    show_debug_message("headerBytes "+string(headerBytes))
    show_debug_message("width "+string(width))
    show_debug_message("height "+string(height))
    show_debug_message("colorPlanes "+string(colorPlanes))
    show_debug_message("bitsPerPixel "+string(bitsPerPixel))
    show_debug_message("compression "+string(compression))
    show_debug_message("dataSize "+string(dataSize))
    show_debug_message("resolutionx "+string(resolutionx))
    show_debug_message("resolutiony "+string(resolutiony))
    show_debug_message("colorsInPalette "+string(colorsInPalette))
    show_debug_message("importantColors "+string(importantColors))
    show_debug_message("AT:  "+string(file_bin_position(file)))
    */
    //goto start of data
    fseek(file,dataOffset,SEEK_SET);
    //rgbalpha
    char r,g,b,forth;
	//pos
    DWORD xx, yy;
	//padding 
    int iend = width % 4;
    int i;
	//get plane 0
	char *a = (char*)arr->planes[0];
    char *start = a;
	//goto last scan line (bmp is revesed on y)
	a+=arr->h*arr->w-arr->w;
	//read data
    for(yy=0;yy<height;yy++)
    {
        for(xx=0;xx<width;xx++)
        {
			//read rgb
            b=getc(file);
            g=getc(file);
            r=getc(file);
			//read alpha
            if(bitsPerPixel == 32)
                forth = getc(file);
			//place in array
			*a = b;
			//next byte
            a++;
        }
		//move up to prev scan line
		a-=arr->w*2;

        //padding at the end of the scanline
        for (i = 0; i < iend; i++) getc(file);
    }

	//close
    fclose(file);

	//return field
    return(double)(DWORD) arr;
}

//this gets the value at the x,y,z position in the 3d filed (array)
gmexport double GMFFFieldGetValue(double field, double x, double y, double z)
{
	int xx,yy,zz;
	xx = (int) x;
	yy = (int) y;
	zz = (int) z;
    //get pointer
    Arr3d *arr = (Arr3d*) (DWORD)field;
    //not null
    if(arr == NULL) return (double)(DWORD) 0;
    //-1 if out of bounds
	if(z<0 || z>=arr->d) return -1;
	if(x<0 || z>=arr->w) return -1;
	if(y<0 || z>=arr->h) return -1;

	//move to x,y position in array
	char *p = (char *) arr->planes[(DWORD)z];
	p+=(DWORD)(xx+yy*arr->w);
    //return value
	return (double)(DWORD)(int) (unsigned char) *p;
}

//faster implementation for local use
Arr3d *_arr;
float _dx,_dy,_dz;
float GetValue(int x, int y, int z)
{


	if(z<0 || z>=_arr->d) return -1;
	if(x<0 || z>=_arr->w) return -1;
	if(y<0 || z>=_arr->h) return -1;

	char *p = (char *) _arr->planes[(DWORD)z];
	p+=(DWORD)(x+y*_arr->w);

	return (float)(int) (unsigned char) *p;
}


//direction matrix to check
int dirs[] = {
-1,-1,-1,   0,-1,-1,   1,-1,-1,
-1, 0,-1,   /*0, 0,-1,*/   1, 0,-1,
-1, 1,-1,   0, 1,-1,   1, 1,-1,

-1,-1, 0,   0,-1, 0,   1,-1, 0,
-1, 0, 0,   /*0, 0, 0,*/   1, 0, 0,
-1, 1, 0,   0, 1, 0,   1, 1, 0,

-1,-1, 1,   0,-1, 1,   1,-1, 1,
-1, 0, 1,   /*0, 0, 1,*/   1, 0, 1,
-1, 1, 1,   0, 1, 1,   1, 1, 1
};

//this calculates a vector from the x,y,z position, looking all all the surounding values
//weighing the result of the direction vectors above with the difference in value
//between the x,y,z point and the surrounding points
//the result is stored in the local global vars _dxyz
gmexport double GMFFFieldComputeVector(double field, double x, double y, double z)
{
	//get pointer, stor in global
    _arr = (Arr3d*) (DWORD)field;
	//null?
	if(_arr == NULL) return 0;
    //reset globals 
	_dx = 0;
	_dy = 0;
	_dz = 0;
	//make sure it's in range
	int xx,yy,zz;
	xx = median(0,(int)x,_arr->w-1);
	yy = median(0,(int)y,_arr->h-1);
	zz = median(0,(int)z,_arr->d-1);

	//define where to start in the dir array
	int istart = 0;
	int iend = 8*3;
    //reduce the lookup table if only 2d
    if(_arr->d == 1) 
	{
		istart = 8;
		iend = 8*2;
	}
	//the value at the position
	float vcenter = GetValue( xx, yy, zz);
    float vat;
	//number of read values
	float ct = 0;
	for(int i = istart; i<iend; i++)
	{
		//read the value
        vat = GetValue( xx+dirs[i*3], yy+dirs[(i*3+1)], zz+dirs[i*3+2]);
		//if read
		if(vat>-1)
		{
			//add to vector, weithed on difference
			_dx+=(float)dirs[i*3] * (float)(vcenter-vat);
			_dy+=(float)dirs[i*3+1] * (float)(vcenter-vat);
			_dz+=(float)dirs[i*3+2] * (float)(vcenter-vat);
			ct+=1;
		}
	}
	//average the vector
	if(ct>0)
	{
		_dx/=ct;
		_dy/=ct;
		_dz/=ct;
	}
	//return success
	return (double) 1.0f;

}
gmexport double GMFFVectorDx()
{
	return (double)_dx;
}
gmexport double GMFFVectorDy()
{
	return (double)_dy;
}
gmexport double GMFFVectorDz()
{
	return (double)_dz;
}
}

Last edited by icuurd12b42 (2011-09-06 02:58:27)

icuurd12b42 · 2011-09-06 03:11:06

Yeah, to be added in the future

FieldAddField(field, filed,x,y,z); //add a field to another such as the displacement field of a unit onto the main field (additive mode)
FieldSetField(field, filed,x,y,z); //set a field to another such as the displacement field of a unit onto the main field (overwrite mode)
FieldReset(field); reset the entire field to 0
FieldClearVolume(field,x,y,z,w,h,d); //resets a portion of the field to 0

I also am thinking of a method to remember what is static (never changing) and what is not, so to make the clearing faster, Like if you have regions that never change, when you clear the field, those would remain, and the non static stuff, those regions would be remembered at add time so only those regions would need to be reset as oppose to resetting the entire set (Field Cube) which could be huge and time consuming.

icuurd12b42 · 2011-09-06 23:38:40

Ok, so it's going well. The zip has been updated and in it you should see the new source. (re-download from main post) By do not use the exe, it's a old compiled, I forgot to re-compile with the working code. Run the gmk

I added the AddField and the ClearField function and now have AIs that want to go to the mouse and avoid each other. (Hit space to add more AIs)

As you can see it behaves somewhat like the video. sure they collide but the point is not for them to avoid that entirely (I think) however it's the way I use the vectors I get from the dll. motion_add is used. So they should distribute themselves evenly while going to the mouse

Now the Add field was implemented faster but I kept having memory overrun issues with my code. so I gave up and used the slower loop in loop for now.

[edit]
Changed the AI to go to the mouse when right mb is down
Added SetField to clear and added a background map

Added clamping from 0 to 255 on FieldAdd, would wrap to 0

Left mb draws the field around the mouse

Last edited by icuurd12b42 (2011-09-07 02:20:32)

xot · 2011-09-07 16:13:31

Seems to work quite well. I'm amazed at how fast this runs. At 100 instance I was getting a steady 140 fps on a 2GHz core.

I ran into an issue I'm sure you've seen where a few entities clumped up together and can't seem to get themselves unstuck again. Seems to happen when they get too close to the mouse pointer. I guess when they get that close they all calculate the same gradient and all go the same direction. It's interesting though. They had a really strong local gradient surrounding them (which guess in some way overpowers the environmental gradient) and they would plow straight through the "hills" in the map. I could see exploiting the different gradient weights to get different behavior from the entities.

I wonder if different gradient shapes and sizes and patterns might produce other interesting behaviors. Perhaps more constrained unit formations might be possible. Perhaps additional gradients at a macro scale could influence unit placement within groups. When I was working on formations for an RTS, one of things that I explored was the placement of different classes of units within the formation (eg. heavies on the front, followed by infantry which escort weaker units in the middle).

Very interesting work.

icuurd12b42 · 2011-09-07 20:51:16

xot wrote:

Seems to work quite well. I'm amazed at how fast this runs. At 100 instance I was getting a steady 140 fps on a 2GHz core.
I ran into an issue I'm sure you've seen where a few entities clumped up together and can't seem to get themselves unstuck again. Seems to happen when they get too close to the mouse pointer. I guess when they get that close they all calculate the same gradient and all go the same direction. It's interesting though. They had a really strong local gradient surrounding them (which guess in some way overpowers the environmental gradient) and they would plow straight through the "hills" in the map. I could see exploiting the different gradient weights to get different behavior from the entities.

I clamp the value from 0 to 255, like a surface; I use a unsigned char array, so yeah. a lot of AIs makes a full value circle. This is resolvable by increasing the distance factor of the check. right now the check at 1 off center. I have a version that uses a float array, but then it's 4 times slower;

You would have to design your ais objects to have collision as a fallback, or arrange your moveto to they dont all try to force there way in. changing the .1 to .2 in the motion add for moving away from the slope... or actually use the slope vector (it holds the force). So the AIs could never climb on top of each other

I wonder if different gradient shapes and sizes and patterns might produce other interesting behaviors. Perhaps more constrained unit formations might be possible. Perhaps additional gradients at a macro scale could influence unit placement within groups. When I was working on formations for an RTS, one of things that I explored was the placement of different classes of units within the formation (eg. heavies on the front, followed by infantry which escort weaker units in the middle).
Very interesting work.

I thought of that too, like a gradient oblique line in front to make the ais pass on the right, or a longer gradient at the front, and a shorter one at the back, or an egg shape. But I dont have rotation in the add field atm.

To form a unit, you could use multiple fields, a weak field in the form of a hole to make units try to get to the same spot combined with the final field, the formation field would not be placed in the final field.

formationfield = loadfield "hole.bmp"
mainfield = createfield
MoveAwayField = loadfield "motionavoid.bmp"

step, Add MoveAway to Main

end step
get dx,dy from hole, relative to center of group
get dx,dy from main field

move according to the combined dx,dy, the local moveaway fields would make the units stay apart while the formation field would hold them together

the result should be a loose formation movement

in a group of multiple types of ais, you could position the tank hole in front of the grunt hole and the support hole would be at the back. 3 formation fields + the main field

As for formation flying... I don't know. Thinking of a field with say 5 holes in it for 5 units to say in a cross pattern, you would have to arrange the MoveAway field so it would invert/overwhelm the each hole in the formation field to prevent 2 units from going in the same hole...

Lots of interesting concepts to try out. Playing with the field and the movement type. I know for sure for simple ai to ai avoidance, this is the fastest way in gm

Last edited by icuurd12b42 (2011-09-07 20:54:15)

icuurd12b42 · 2011-09-08 16:36:35

Well, I'm abandoning this for now... It's all very interesting and if anyone wants to take it over, go ahead. I decided to start implementing another method which should yield the same avoidance signal while having a smaller memory footprint and faster vector calculation

icuurd12b42 · 2011-10-10 23:24:12

Here's a re-implementation using circular regions... Based on distance between 2 points on touching circles

http://gmc.yoyogames.com/index.php?showtopic=521613

Last edited by icuurd12b42 (2011-10-10 23:24:40)

GMLscripts.com

#1 2011-09-06 02:57:31

Flowfield implemetation

#2 2011-09-06 03:11:06

Re: Flowfield implemetation

#3 2011-09-06 23:38:40

Re: Flowfield implemetation

#4 2011-09-07 16:13:31

Re: Flowfield implemetation

#5 2011-09-07 20:51:16

Re: Flowfield implemetation

#6 2011-09-08 16:36:35

Re: Flowfield implemetation

#7 2011-10-10 23:24:12

Re: Flowfield implemetation

Board footer