Author Topic: Problem with recursive function  (Read 12048 times)

0 Members and 1 Guest are viewing this topic.

VorpalBlade

  • World Machine Guru
  • ****
  • Posts: 55
    • View Profile
Problem with recursive function
« on: October 31, 2006, 01:36:01 AM »
This is frustrating me. The following plugin works in the little preview window, however the program closes when I generate terrain. It doesn't give an error or pop-up a debugger so I'm clueless as to what is causing it. I can get it to work by commenting out some code in a recurcive function...

Code: [Select]
#include "stdafx.h"
#include "inverter.h"
#include "..\core\HField.h"

// You must furnish your own Maker and Killer functions. The Maker should (obviously) be unique for each device,
// while the Killer can be shared among plugins in the same DLL. The basic idea is to get around the sometimes-messy
// problem of DLL<->Client heap management. The framework will call your maker and killers as appropriate.


Device *InverterMaker() { return new Inverter; };
void InverterKiller(Device *spr) { delete spr; };

struct Point {
         int x;
         int y;
float z;
};
bool FindBasin(HField*, Point*);
void SetFillHeight(HField*, HField*, Point*);
bool AreaIsBasin(HField*, HField*, int, int, float);
void ClearHField(HField*);
void AddBasinToMask(HField*, HField*);
bool PointIsEdge(HField*, int, int);


// What you MUST DO in the constructor of your device:
// 1) Set the Nametag, Maker and Killer in the lifeptrs struct.
// What you SHOULD do in the constructor:
// 2) Call SetLinks() with the # of inputs and outputs your device is going to use
//      ...if you dont do #2, you will use the default # of inputs your parent class assigns
Inverter::Inverter(void)
{
lifeptrs.maker = InverterMaker;
lifeptrs.killer = InverterKiller;
strncpy(lifeptrs.nametag, "EX_IV", 4);
SetLinks(1, 1);
// This is how you would add a parameter to a device that is managed by the generic dlg system
// This adds a floating point parameter. You can add floats, ints, bools, or enums.
AddParam(Parameter("Dummy Parameter", 0.0f, 0.0f, 1.0f));
}

// This is a convenient way to access your device parameters
// Note that accessing parameters is really quite slow due to the string searching for the param name.
// Do NOT call inside of loops if you care about performance -- just retrieve the value once and cache it.
#define INV_DUMMY ParmFRef("Dummy Parameter")


Inverter::~Inverter(void)
{

}

// You are REQUIRED to write out and read in your 4-byte Device ID tag, as shown below. It is also recommended that your device
// have an internal version number that you keep track of to allow backwards-compatibility if you ever change your Device save layout...
// Also, make sure you call your super class's Load and Save functions as shown here. Failure to do so will cause major problems.
bool Inverter::Load(std::istream &in) {
char tag[5];
in.read( tag, 4);
if (strncmp(tag, lifeptrs.nametag, 4) == 0) {
int ver = 0;
in.read((char*) &ver, 1);
return Filter::Load(in);
}
else
return false;
};

bool Inverter::Save(std::ostream &out) {
out.write( lifeptrs.nametag, 4);
int ver = 1;
out.write((char*) &ver, 1);
return Filter::Save(out);
};

// The Activate function is where you work your magic. You should do four things in the Activate function:
// 1) Retrieve your inputs by calling RetrieveData(input#)
// 2) Do whatever you will do on it...
// 3) Store the data to make it available to your outputs
// 4) Return true to indicate successful activation, or false if there was an error.
bool Inverter::Activate(int pstate) {
HField *hf = HF(RetrieveData(0) ); // Use the RetrieveData(),StoreData() pair to get and set your heightfields
    HField *hfMask = GetNewHF(GetWorldSize());
HField *hfTemp = GetNewHF(GetWorldSize());
Point *pBasin = new Point();
// This is important! An input CAN RETURN NULL if it is not connected, or the input is turned off. So always check and bail out if its not there
if (!hf)
return false;

// ** example: if we actually DID anything with our dummy param, this is how you would get it
float dummy = INV_DUMMY;

// ** example: If you wanted to access the data by coordinate instead of by index, here's how you would do it:
int width = hf->w();
int height = hf->h();

// Find basin low points

for (int x = width/2; x < width; x=x+width) {
for (int y = height/2; y < height; y=y+height) {
pBasin->x = x;
pBasin->y = y;
if (FindBasin(hf, pBasin)) {
// (*hf)[Coord(pBasin->x, pBasin->y)] = 1.0f; // test basin points (remove)
SetFillHeight(hf, hfTemp, pBasin);
AddBasinToMask(hfMask, hfTemp);
}
}
}

// Handoff to output(s)
StoreData(hfTemp,0); // pass the heightfield to our output stage.
// Success!
delete pBasin; // take out the trash.
return true;
}

bool FindBasin(HField* hf, Point* p) {
int lowX = p->x;
int lowY = p->y;
if (PointIsEdge(hf, p->x, p->y)) // return false if current point is on edge of map.
return FALSE;
for (int northToSouth = 1; northToSouth > -2; northToSouth--) { // Find lowest point in 3x3 grid.
for (int westToEast = -1; westToEast < 2; westToEast++) {
if ((*hf)[Coord(lowX, lowY)] > (*hf)[Coord(p->x+westToEast, p->y+northToSouth)]) { // reset lowest point if lower than current.
lowX = p->x+westToEast;
lowY = p->y+northToSouth;
}
}
}
if (lowX == p->x && lowY == p->y) { // if current point is lowest point set z and return TRUE.
p->z = (*hf)[Coord(p->x, p->y)];
return TRUE;
} else {
p->x = lowX;
p->y = lowY;
return FindBasin(hf, p); // set current point to lowest point and do it again.
}
}

void SetFillHeight(HField* hf, HField* hfT, Point* p) { // Finds and sets the basin area to the mask.
bool lastOK;
float maxZ = 1.0f;
float lastGoodZ = p->z;
if (AreaIsBasin(hf, hfT, p->x, p->y, p->z)) {
p->z = (p->z + maxZ) * 0.5f;
for (int i = 0; i < 5; ++i) {
ClearHField(hfT);
if (AreaIsBasin(hf, hfT, p->x, p->y, p->z)) {
lastGoodZ = p->z;
p->z = (p->z + maxZ) * 0.5f;
lastOK = TRUE;
} else {
maxZ = p->z;
p->z = (maxZ + lastGoodZ) * 0.5f;
lastOK = FALSE;
}
}
if (!lastOK)
ClearHField(hfT);
AreaIsBasin(hf, hfT, p->x, p->y, lastGoodZ);
}
}

bool AreaIsBasin(HField* hf, HField* hfT, int x, int y, float z) {  // returns true if elevation of p->z creates a basin.
if (PointIsEdge(hf, x, y)) {                                    // This is a border point. Basin spills.
return FALSE;
} else if ((*hf)[Coord(x,y)] > z || (*hfT)[Coord(x,y)] > 0.0f)    // Dead end. So far so good.
return TRUE;
else {                                                          // If all avenues lead to deadends, we got a basin at height z.
(*hfT)[Coord(x,y)] = 1.0f;
return ( AreaIsBasin(hf, hfT, x, y+1, z) &&
AreaIsBasin(hf, hfT, x-1, y+1, z) &&
AreaIsBasin(hf, hfT, x-1, y, z) &&
AreaIsBasin(hf, hfT, x-1, y-1, z) &&
AreaIsBasin(hf, hfT, x, y-1, z) &&
AreaIsBasin(hf, hfT, x+1, y-1, z) &&
AreaIsBasin(hf, hfT, x+1, y, z) &&
AreaIsBasin(hf, hfT, x+1, y+1, z) );
}
}

void ClearHField(HField* hf) { // zeros out height of hf.
int width = hf->w();
int height = hf->h();
for (int x = 0; x < width; ++x) {
for (int y = 0; y < height; ++y)
(*hf)[Coord(x,y)] = 0.0f;
}
}

void AddBasinToMask(HField* hfMask, HField* hfTemp) {

}

bool PointIsEdge(HField* hf, int x, int y) {
if (x-1 < 0 || x+1 > hf->w() || y-1 < 0 || y+1 > hf->h()) // return true if current point is on edge of map.
return TRUE;
else
return FALSE;
}

If I comment out as follows it works....

Code: [Select]
bool AreaIsBasin(HField* hf, HField* hfT, int x, int y, float z) {  // returns true if elevation of p->z creates a basin.
if (PointIsEdge(hf, x, y)) {                                    // This is a border point. Basin spills.
return FALSE;
} else if ((*hf)[Coord(x,y)] > z || (*hfT)[Coord(x,y)] > 0.0f)    // Dead end. So far so good.
return TRUE;
else {                                                          // If all avenues lead to deadends, we got a basin at height z.
(*hfT)[Coord(x,y)] = 1.0f;
return ( AreaIsBasin(hf, hfT, x, y+1, z) &&
AreaIsBasin(hf, hfT, x-1, y+1, z) &&
// AreaIsBasin(hf, hfT, x-1, y, z) &&
// AreaIsBasin(hf, hfT, x-1, y-1, z) &&
// AreaIsBasin(hf, hfT, x, y-1, z) &&
AreaIsBasin(hf, hfT, x+1, y-1, z) &&
AreaIsBasin(hf, hfT, x+1, y, z) &&
AreaIsBasin(hf, hfT, x+1, y+1, z) );
}
}

Any ideas?

nikita

  • Testing Team
  • World Machine Guru
  • *****
  • Posts: 627
  • B.S. in Macro Science
    • View Profile
    • My WM Macros
Re: Problem with recursive function
« Reply #1 on: October 31, 2006, 05:13:43 AM »
Imagine you basin is 3 points high and 4 wide (4x3):
- You call AreaIsBasin() for the point at (2,2).
- AreaIsBasin(2,2) (simplified) calls AreaIsBasin() eight times for the surrounding points, thus it also calls AreaIsBasin(3,2)
- now AreaIsBasin(3,2) calls AreaIsBasin(2,2)
- now AreaIsBasin(2,2) calls AreaIsBasin(3,2)
Infinite Loop   :)
"Every time you read or write beyond the end of an array, somewhere a fairy dies."
Richard Buckland

Fil

  • Testing Team
  • World Machine Guru
  • *****
  • Posts: 550
    • View Profile
Re: Problem with recursive function
« Reply #2 on: October 31, 2006, 06:34:37 AM »
First off (and not meaning to be rude) I didn't read all your code up there :)
But if Nikita is right about what is happening, you need to end the recursion somewhere, so you need to know the "depth" in the tree of calls to functions. (typically a parameter can be used, like calling areaIsBasin(int x, int y, int depth), and checking the depth for knowing what to do inside the function.

If you'd like to "keep track" of where you've looked in the main height field and where you haven't, you may find it useful to get a new HF with the same size, but set to zero, and when you traverse your original HF, you set this one to a value higher than zero. You can even count the number of times youve consulted it, if you increment a value.  Don't forget to call "->release();" on that auxiliary HF, so that you cause memory leaks, each time you move a slider or build the network :)
Fil.

VorpalBlade

  • World Machine Guru
  • ****
  • Posts: 55
    • View Profile
Re: Problem with recursive function
« Reply #3 on: October 31, 2006, 01:39:51 PM »
Imagine you basin is 3 points high and 4 wide (4x3):
- You call AreaIsBasin() for the point at (2,2).
- AreaIsBasin(2,2) (simplified) calls AreaIsBasin() eight times for the surrounding points, thus it also calls AreaIsBasin(3,2)
- now AreaIsBasin(3,2) calls AreaIsBasin(2,2)
- now AreaIsBasin(2,2) calls AreaIsBasin(3,2)
Infinite Loop   :)

It cannot be an infinate loop because every point that is checked is marked and does not continue if it has been marked.

else if ((*hf)[Coord(x,y)] > z || (*hfT)[Coord(x,y)] > 0.0f)        // If its above the height or if it has already been checked then return
  return TRUE;
else {                                                         
  (*hfT)[Coord(x,y)] = 1.0f;                                                 // marks it as already checked then continues to surrounding points.
  return ( AreaIsBasin(hf, hfT, x, y+1, z) &&...



VorpalBlade

  • World Machine Guru
  • ****
  • Posts: 55
    • View Profile
Re: Problem with recursive function
« Reply #4 on: October 31, 2006, 01:43:05 PM »
If you'd like to "keep track" of where you've looked in the main height field and where you haven't, you may find it useful to get a new HF with the same size, but set to zero, and when you traverse your original HF, you set this one to a value higher than zero...

Right! Which is exatly what I did (HField* hfT). So it isnt a runnaway recursion.

I also tried ->release(); but it appears that that method isn't included in HField.
« Last Edit: October 31, 2006, 01:49:42 PM by VorpalBlade »

VorpalBlade

  • World Machine Guru
  • ****
  • Posts: 55
    • View Profile
Re: Problem with recursive function
« Reply #5 on: October 31, 2006, 03:17:45 PM »
Is it possible that there is a problem in the way I am generateing the temp HField?

HField *hf = HF(RetrieveData(0) );
HField *hfTemp = GetNewHF(GetWorldSize());

Will these two be equal in size? Or should i copy the first and zero it out?

Remnant

  • Author
  • World Machine Guru
  • *****
  • Posts: 2311
    • View Profile
    • http://www.world-machine.com/
Re: Problem with recursive function
« Reply #6 on: October 31, 2006, 04:04:46 PM »
That method is fine in the current WM for creating similar-sized heightfields.

There's a couple things I can think of that might be going on:

First, I would check all boundary conditions -- make absolutely sure that you're never going to be addressing a point outside of the heightfield.

The HF class already has a function for this purpose for reading; instead of using the assignment operator or the value function, use the valueSafe function (see HField.h)

If that's not the problem, and especially if it works for smaller heightfields but bombs for larger, you might be blowing out the stack. I forget what the default stack size is, and it's pretty large so this seems unlikely to me, but it is something to always be aware of with recursive algorithms. Check it with different sized heightfields and see if there's a value it starts blowing up on, or if it always fails or always works.



-- Stephen Schmitt
- Creator of World Machine

VorpalBlade

  • World Machine Guru
  • ****
  • Posts: 55
    • View Profile
Re: Problem with recursive function
« Reply #7 on: October 31, 2006, 06:29:55 PM »
Thanks Remnant,

I think there may be a way (with uglier code) to trim down the stack size. Although I agree it doesn't seem right for the fact that it is only anylizing a small chunk of the whole heightfield at a time. Also the stack should unwind many times before ever getting too big due the the checks and returns.

I'll try reducing the generate terrain size and give that valueSafe function a try.

Thanks!

VorpalBlade

  • World Machine Guru
  • ****
  • Posts: 55
    • View Profile
Re: Problem with recursive function
« Reply #8 on: October 31, 2006, 08:42:23 PM »
Not sure if this would do much to decrease the size of the stack or not, but that function currently passes two ints and a float by value. I have been taught that ints and floats are to insignificant to pass by ref but I was wondering if I create a new Point struct which contains all three in HEAP, and just pass a pointer (destroying it of course when the stack unwinds). would that be smaller than the  int, int, float combined?

VorpalBlade

  • World Machine Guru
  • ****
  • Posts: 55
    • View Profile
Re: Problem with recursive function
« Reply #9 on: November 01, 2006, 02:41:30 AM »
Ok, I progressively increased the resolution of the build and it seems to bomb at 256x256. All the lower resolutions build. So does this point to a stack overflow?

Thanks again to everyone!

JavaJones

  • World Machine Guru
  • ****
  • Posts: 410
    • View Profile
    • http://oshyan.ashundar.com
Re: Problem with recursive function
« Reply #10 on: November 17, 2006, 01:15:17 PM »
I'm afraid I can't contribute anything meaningful here, but I thought I'd "bump" this thread in the hopes that others might give more input. I always like seeing more plugins. :)

- Oshyan

VorpalBlade

  • World Machine Guru
  • ****
  • Posts: 55
    • View Profile
Re: Problem with recursive function
« Reply #11 on: November 17, 2006, 10:39:31 PM »
Thank you very much Java  :lol:

However, I just upgraded and reformatted my harddrive so I've actually been pulled away from it for a bit. I do have one question from other plugin builders if they use recursion and if so, I wouldn't mind a little sample of a recursive function that they know to work. Then I could work up from there.

Thanks

Fil

  • Testing Team
  • World Machine Guru
  • *****
  • Posts: 550
    • View Profile
Re: Problem with recursive function
« Reply #12 on: November 18, 2006, 05:31:15 AM »
Recursion is a bit of a pain if not done very carefully.. The hardest part is always to debug it :P
I've not done any recursive maneuvers in a plug-in for WM yet. I've been afraid of it :)
I had a few ideas for stuff to do that involved recursion, but for those I've always thought of making my own stand alone application to try it out before putting it in the PDK. Personally I'm not really at ease with the idea of using the MSVC debugger on WM without the source code for WM it self, so there can be a lot of calls WM stuff, that I can't follow very well. So, to avoid debugging *in* WM, I would suggest coding your classes outside, workout if they're behaving well, and then throw them in the PDK afterwards.
You may need to write some interface code for giving it a BMP image and writing a bmp image for output, to test it. BMPs and TGAs are among the easiest file formats to write.. Though, you can also use PNG..  But most of the essential stuff can be tested by looking at the numbers :P (But it's not as hard as debugging "The Matrix" ;))
Fil.