   Maze Algorithm not working properly
  I've written code to draw a random "perfect maze" as defined in the following link: http://www.astrolog.org/labyrnth/algrithm.htmBut its not drawing the maze walls. I think I've narrowed the problem down to the function called "eNumConnected" which is supposed to count the number of solid walls connected to edge being considered.I've double checked the calculations it makes and I've double checked everything else too, but the problem persists.Here is the source code for the whole program:#include <windows.h>#include <windowsx.h>#include <d3d9.h>#include <d3dx9.h>#include <time.h>//include the Direct3D Library files#pragma comment (lib, "d3d9.lib")#pragma comment (lib, "d3dx9.lib")#define Pi 3.1416f#define SCREEN_WIDTH 1280#define SCREEN_HEIGHT 800#define DefaultBackgroundColour D3DCOLOR_XRGB(0, 0, 0)#define mCol D3DCOLOR_XRGB(0, 0, 255)#define mSpacing 2.0f#define mDim 10#define ePOSSIBLE 0#define eENTRY 1#define eEXIT 2#define eEMPTY 3#define eSOLID 4LPDIRECT3D9 d3d=NULL;LPDIRECT3DDEVICE9 d3ddev=NULL;LPDIRECT3DVERTEXBUFFER9 vbLine = NULL;struct CUSTOMVERTEX {FLOAT X, Y, Z; DWORD COLOR;};LRESULT CALLBACK WindowProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam);#define CUSTOMFVF (D3DFVF_XYZ | D3DFVF_DIFFUSE)class Edge{private:float X;float Y;float Angle;int Type; //E_POSSIBLE, E_ENTRY, E_EXIT, E_EMPTY, E_SOLIDpublic:void SetX(float x){ X = x; }void SetY(float y){ Y = y; }void SetA(float A){ Angle = A; }void SetT(int T){ Type = T; }float GetX(){ return X;}float GetY(){ return Y; }float GetA(){ return Angle; }int GetT(){ return Type; }};Edge eMaze[mDim][2*mDim+2];void InitD3D(HWND hWnd);void CleanProgram(void);void RenderFrame(void);void InitGraphics(void);bool IsMazeComplete();int eNumConnected(int i, int j);int WINAPI WinMain(HINSTANCE hInstance,    HINSTANCE hPrevInstance,    LPSTR lpCmdLine,    int nCmdShow){srand ( time(NULL) );    HWND hWnd;    WNDCLASSEX wc;    ZeroMemory(&wc, sizeof(WNDCLASSEX));    wc.cbSize = sizeof(WNDCLASSEX);    wc.style = CS_HREDRAW | CS_VREDRAW;    wc.lpfnWndProc = WindowProc;    wc.hInstance = hInstance;    wc.hCursor = LoadCursor(NULL, IDC_ARROW);    wc.lpszClassName = L"WindowClass";    RegisterClassEx(&wc);    hWnd = CreateWindowEx(NULL, L"WindowClass", L"Mazes", WS_OVERLAPPEDWINDOW, 0, 0, SCREEN_WIDTH, SCREEN_HEIGHT, NULL, NULL, hInstance, NULL);    ShowWindow(hWnd, nCmdShow);    InitD3D(hWnd);InitGraphics();    MSG msg;    while(TRUE)    {   while(PeekMessage(&msg, NULL, 0, 0, PM_REMOVE))   {  TranslateMessage(&msg);  DispatchMessage(&msg);   }   if(msg.message == WM_QUIT)  break;   RenderFrame();    }    CleanProgram();    return msg.wParam;}LRESULT CALLBACK WindowProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam){    switch(message)    {   case WM_DESTROY:  { PostQuitMessage(0); return 0;  } break;    }    return DefWindowProc (hWnd, message, wParam, lParam);}void InitD3D(HWND hWnd){    d3d = Direct3DCreate9(D3D_SDK_VERSION);    D3DPRESENT_PARAMETERS d3dpp;    ZeroMemory(&d3dpp, sizeof(d3dpp));    d3dpp.Windowed = TRUE;    d3dpp.SwapEffect = D3DSWAPEFFECT_DISCARD;    d3dpp.hDeviceWindow = hWnd;    d3dpp.BackBufferFormat = D3DFMT_X8R8G8B8;    d3dpp.BackBufferWidth = SCREEN_WIDTH;    d3dpp.BackBufferHeight = SCREEN_HEIGHT;    d3dpp.EnableAutoDepthStencil = TRUE;    d3dpp.AutoDepthStencilFormat = D3DFMT_D16;    d3d->CreateDevice(D3DADAPTER_DEFAULT,  D3DDEVTYPE_HAL,  hWnd,  D3DCREATE_SOFTWARE_VERTEXPROCESSING,  &d3dpp,  &d3ddev);    d3ddev->SetRenderState(D3DRS_LIGHTING, FALSE);    // turn off the 3D lighting    d3ddev->SetRenderState(D3DRS_CULLMODE, D3DCULL_NONE);    // turn off culling    d3ddev->SetRenderState(D3DRS_ZENABLE, TRUE);    // turn on the z-buffer}void CleanProgram(void){d3ddev->Release();    d3d->Release();vbLine->Release();}void RenderFrame(void){    d3ddev->Clear(0, NULL, D3DCLEAR_TARGET, DefaultBackgroundColour, 1.0f, 0);    d3ddev->Clear(0, NULL, D3DCLEAR_ZBUFFER, DefaultBackgroundColour, 1.0f, 0);    d3ddev->BeginScene();    d3ddev->SetFVF(CUSTOMFVF);    // set the view transform    D3DXMATRIX mView;    // the view transform matrix    D3DXMatrixLookAtLH(&mView,    &D3DXVECTOR3 (0.0f, 0.0f, 100.0f),    // the camera position    &D3DXVECTOR3 (0.0f, 0.0f, 0.0f), // the look-at position    &D3DXVECTOR3 (0.0f, 1.0f, 0.0f));    // the up direction    d3ddev->SetTransform(D3DTS_VIEW, &mView);    // set the view transform to matView    // set the projection transform    D3DXMATRIX mProjection;    // the projection transform matrix    D3DXMatrixPerspectiveFovLH(&mProjection, D3DXToRadian(45),    // the horizontal field of view (FLOAT)SCREEN_WIDTH / (FLOAT)SCREEN_HEIGHT, // aspect ratio 1.0f,   // the near view-plane 100.0f);    // the far view-plane    d3ddev->SetTransform(D3DTS_PROJECTION, &mProjection); // set the projection/*//test drawing of primitive lined3ddev->SetStreamSource(0, vbLine, 0, sizeof(CUSTOMVERTEX));D3DXMATRIX mRotate; D3DXMatrixRotationZ(&mRotate, Pi/3);D3DXMATRIX mTranslate;D3DXMatrixTranslation(&mTranslate, 0.0f, 0.0f, 0.0f);d3ddev->SetTransform(D3DTS_WORLD, &(mRotate*mTranslate));d3ddev->DrawPrimitive(D3DPT_LINELIST, 0, 1);*///Center view on maze space and draw the mazeD3DXMatrixLookAtLH(&mView,    &D3DXVECTOR3 (mDim*mSpacing/2, mDim*mSpacing/2, 100.0f),    // the camera position    &D3DXVECTOR3 (mDim*mSpacing/2, mDim*mSpacing/2, 0.0f), // the look-at position    &D3DXVECTOR3 (0.0f, 1.0f, 0.0f));    // the up direction    d3ddev->SetTransform(D3DTS_VIEW, &mView);d3ddev->SetStreamSource(0, vbLine, 0, sizeof(CUSTOMVERTEX));D3DXMATRIX mTranslate;D3DXMATRIX mRotate;for(int i=0; i<mDim; i++){for(int j=0; j<(2*mDim+2); j++){if(eMaze[j].GetT() == eSOLID) {D3DXMatrixRotationZ(&mRotate, eMaze[j].GetA());D3DXMatrixTranslation(&mTranslate, eMaze[j].GetX(), eMaze[j].GetY(), 0.0f);d3ddev->SetTransform(D3DTS_WORLD, &(mRotate*mTranslate));d3ddev->DrawPrimitive(D3DPT_LINELIST, 0, 1);if(j%2){D3DXMatrixRotationZ(&mRotate, eMaze[j].GetA());D3DXMatrixTranslation(&mTranslate, eMaze[j].GetX()+0.1f, eMaze[j].GetY(), 0.0f);d3ddev->SetTransform(D3DTS_WORLD, &(mRotate*mTranslate));d3ddev->DrawPrimitive(D3DPT_LINELIST, 0, 1);}else{D3DXMatrixRotationZ(&mRotate, eMaze[j].GetA());D3DXMatrixTranslation(&mTranslate, eMaze[j].GetX(), eMaze[j].GetY()+0.1f, 0.0f);d3ddev->SetTransform(D3DTS_WORLD, &(mRotate*mTranslate));d3ddev->DrawPrimitive(D3DPT_LINELIST, 0, 1);}}}}    d3ddev->EndScene();d3ddev->Present(NULL, NULL, NULL, NULL);}void InitGraphics(void){////LINE PRIMITIVE//CUSTOMVERTEX vLine[] =    {   { 0.0f, 0.0f, 0.0f, mCol},   { mSpacing, 0.0f, 0.0f, mCol}    };d3ddev->CreateVertexBuffer(2*sizeof(CUSTOMVERTEX),0,CUSTOMFVF,D3DPOOL_MANAGED,&vbLine,NULL);VOID* pLineVoid;    // a void pointer    // lock v_buffer and load the vertices into it    vbLine->Lock(0, 0, (void**)&pLineVoid, 0);    memcpy(pLineVoid, vLine, sizeof(vLine));    vbLine->Unlock();////MAZE PRIMITIVE////Initiate maze.for(int i=0; i<mDim; i++){for(int j=0; j<(2*mDim+2); j++){if(j % 2){eMaze[j].SetX(mSpacing*j/2 - mSpacing/2);eMaze[j].SetY(i*mSpacing);}else{eMaze[j].SetX(i*mSpacing);eMaze[j].SetY(mSpacing*j/2);}if(j % 2){ eMaze[j].SetA(Pi/2); }else{ eMaze[j].SetA(0.0f); }eMaze[j].SetT(ePOSSIBLE);}}//Set all outer edges as solidfor(int i=0; i<mDim; i++){eMaze[0].SetT(eSOLID);eMaze[1].SetT(eSOLID);eMaze[2*mDim].SetT(eSOLID);eMaze[2*mDim+1].SetT(eSOLID);}//pick 2 outer walls on opposite boundaries and make them entry and exiteMaze[rand() % mDim][0].SetT(eENTRY);eMaze[rand() % mDim][2*mDim].SetT(eEXIT);//pick a random possible edge on each line and turn into the appropriate type//keep doing this till maze is completeint i; int j;int test = 0;while(!IsMazeComplete() && test<10000000){i = rand() % (mDim); j = 2 + rand() % (2*mDim - 2);if(eMaze[j].GetT()==ePOSSIBLE){if(eNumConnected(i, j) == 1){ eMaze[j].SetT(eSOLID); }if(eNumConnected(i, j) > 1){ eMaze[j].SetT(eEMPTY); }test++;}}}bool IsMazeComplete(){for(int i=0; i<mDim; i++){for(int j=2; j<(2*mDim+2); j++){if(eMaze[j].GetT() == ePOSSIBLE){ return 0; }}}return 1;}int eNumConnected(int i, int j){int NumConnected = 0;if(j % 2){if( eMaze[(j-3)/2][2*i].GetT() == eSOLID ){ NumConnected++; }if( eMaze[(j-3)/2 + 1][2*i+2].GetT() == eSOLID ){ NumConnected++; }if( eMaze[(j-3)/2][2*i].GetT() == eSOLID ){ NumConnected++; }if( eMaze[(j-3)/2 + 1][2*i+2].GetT() == eSOLID ){ NumConnected++; }if( i>0 && eMaze[i-1][j].GetT() == eSOLID ){ NumConnected++; }if( i<(mDim-1) && eMaze[i+1][j].GetT() == eSOLID ) { NumConnected++; }}else{if( eMaze[(j-2)/2][i*2 +1].GetT() == eSOLID ){ NumConnected++; }if( eMaze[(j-2)/2 + 1][i*2 +3].GetT() == eSOLID ){ NumConnected++; }if( eMaze[(j-2)/2][i*2 +1].GetT() == eSOLID ){ NumConnected++; }if( eMaze[(j-2)/2 + 1][i*2 +3].GetT() == eSOLID ){ NumConnected++; }if( i>0 && eMaze[i-1][j].GetT() == eSOLID ){ NumConnected++; }if( i<(mDim-1) && eMaze[i+1][j].GetT() == eSOLID ){ NumConnected++; }}return NumConnected;}
  Try the D3D debug runtime.Is it drawing anything at all? Also, why are you setting the view matrix twice?If you think the problem is in eNumConnected(), you should test it in a separate small console program that just calls the function with various values and checks if the function returns the correct values.In other words, first make sure that the maze-related code works, then add the drawing code.   ;Quote:Original post by Gage64Try the D3D debug runtime.Is it drawing anything at all? Also, why are you setting the view matrix twice?If you think the problem is in eNumConnected(), you should test it in a separate small console program that just calls the function with various values and checks if the function returns the correct values.In other words, first make sure that the maze-related code works, then add the drawing code.Hi, thanks for the reply :)---I tried the debug version and it came up with this error a few times:"Direct3D9: (ERROR) :ASSERTION FAILED! File s:\gfx_aug09\windows\directx\dxg\inactive\d3d9\d3d\fw\lhbatchfilter.cpp Line 3466: pArgs->Flags.Discard"Though I have no idea what that means. Google yielded no results as far as I could tell.---It is drawing the outer walls of the maze properly, including the entry and exit at the right places. But it does not draw any of the edges inside the outer walls. But it only draws what it does because I artificially set the "while(!IsMazeComplete())" loop to terminate when am int counter labelled "test" reaches 10,000,000. Without that condition the program hangs and draws nothing, as if it were stuck in an endless loop.---I'm setting the view matrix twice because I plan to do more with this program that just draw the maze. I want to turn it into a mini game and draw an intro screen before I draw the maze.---Actually after thinking about it a bit more, the alogrithm I'm trying to create the maze with could also be wrong. IMO its either the algorithm or the eNumConnected function. I will follow your advice and test it separately.Thanks again.   ;  About the failed assertion - when calling CreateDevice(), are you using D3DCREATE_SOFTWARE_VERTEXPROCESSING? If so, try changing it to D3DCREATE_HARDWARE_VERTEXPROCESSING.I got that from here.   ;Quote:Original post by Gage64About the failed assertion - when calling CreateDevice(), are you using D3DCREATE_SOFTWARE_VERTEXPROCESSING? If so, try changing it to D3DCREATE_HARDWARE_VERTEXPROCESSING.I got that from here.Yup, that fixed that problem. Thank you very much :)---I've decided I don't like the general maze algorithm I was trying to use. I have no proof that it actually works, or that it produces "good" mazes. Also it depends almost entirely on eNumConnected and eNumConnected is imo a nightmare to work with.---I'll try and look for a more well documented maze generation algorithm. Any one got any suggestions?All is not lost though because I still have the basic engine for the program, and I can still get as far as drawing the outer walls of the maze and the entry and exit.   ;  Take a look here. It might be a bit basic (I haven't looked at it too thoroughly), but it might still contain some useful information.   ;  You might find the  solutions thread for that project useful as well.   ;  Thanks for the suggestions guys.I especially like the method you posted Gage64. Will redo my program to use that algorithm.   