You are not logged in.
Pages: 1
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)
// 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)
Offline
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.
Offline
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)
Offline
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.
Abusing forum power since 1986.
Offline
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)
Offline
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
Offline
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)
Offline
Pages: 1