First , though, let me apologize for the delays. With the news about Aces, LRB at GDC, and the LRB Native Title Ops Reviews I have been running my time has been at a premium. So here I am stealing time on a Saturday. Onwards.
What we need is a way to mark a cell as visited, and then a way to walk the cells looking for unvisited cells and mark them. And then once there are no more cells, to restart. Note, it would be a little more interesting to generate a new maze when done, but we will leave that for a future article. At this point a restart amounts to clearing all cells to the unvisited state and moving to the initial cell, rinse, and repeat. It would also be even more interesting to set a “goal” of a “final location”, set a random starting point, and add some rendering to the start and finish cells. Perhaps we’ll see that for a couple other, future articles.
First, though, a few improvements I noticed over the last couple of weeks. And then this installment of the series.
Two “behaviors”
For those of you paying attention, in previous articles the rendering in D3D10 was substantially lighter than D3D9, for instance:
That was due to the fact that since the Mar 2008 SDK the DXUT framework has gamma correction on by default.
We call DXUTSetIsInGammaCorrectMode(false) to disable it, and now we have:
D3D9 with gamma off.
D3D10 with gamma off
In terms of image quality and color balance, now D3D10 and D3D9 rendering match.
The next thing I noticed is the key handling code in FrameMove using GetAsyncKeyState, is inherently problematic. Let’s move that handling to the natural place for it, the KeyboardProc. We move
//handle key presses
if( GetAsyncKeyState( VK_SHIFT ) & 0x8000 )
{
}
else
{
if( GetAsyncKeyState( 'M' ) & 0x8000 )
{
g_bSelfCam = true;
g_bSkyCam = false;
}
if( GetAsyncKeyState( 'K' ) & 0x8000 )
{
g_bSelfCam = false;
g_bSkyCam = true;
}
if ( GetAsyncKeyState( 'P' ) & 0x8000 )
{
g_bRunSim = !g_bRunSim;
}
}
//handle key presses
if( GetAsyncKeyState( VK_SHIFT ) & 0x8000 )
{
}
else
{
if( GetAsyncKeyState( 'M' ) & 0x8000 )
{
g_bSelfCam = true;
g_bSkyCam = false;
}
if( GetAsyncKeyState( 'K' ) & 0x8000 )
{
g_bSelfCam = false;
g_bSkyCam = true;
}
if ( GetAsyncKeyState( 'P' ) & 0x8000 )
{
g_bRunSim = !g_bRunSim;
}
}
To
void CALLBACK OnKeyboard( UINT nChar, bool bKeyDown, bool bAltDown, void* pUserContext )
{
if( bKeyDown )
{
switch( nChar )
{
case 'K':
g_bSelfCam = false;
g_bSkyCam = true;
break;
case 'M':
g_bSelfCam = true;
g_bSkyCam = false;
break;
case 'P':
g_bRunSim = !g_bRunSim;
break;
}
}
}
Ok, that catches us up on wierdities I have noticed.
I will not go back and touch up the previous proects, but feel free to do so. And if someone does, please provide a comment and a link so other readers can benefit from your work.
The Solver Project
Here is a screenshot of the updated project, with the CSim-Navigation source/header file pair added:
Solution Window
We’ll cover the changes in 3 sections: Cells, Visits, and Traversals, Callback Changes, and Conclusion.
Cells, Visits, and Traversals
We need a way to mark cells. We’ll define a struct and a simple stack template to contain our visited cells:
struct AutopilotCell
{
AutopilotCell() {};
AutopilotCell( BYTE X , BYTE Y ) : x(X),y(Y) {};
BYTE x,y;
};
SimpleStack m_AutopilotStack;
BYTE m_AutopilotVisited[MAZE_MAX_WIDTH][MAZE_MAX_HEIGHT];
Then we need some “control” functions:
void StartNavigation();
void StepNavigation(float fElapsedTime);
void PickAutopilotTarget();
void EngageAutopilot(BOOL bEngage);
void DoAutopilot(FLOAT fElapsed);
StartNavigation simply sets up some control variables:
void StartNavigation()
{
//set autopilot/self cam ivars
m_aCameraYaw = 0;
m_vCameraPos.x = 0.0f;
m_vCameraPos.y = 0.5f;
m_vCameraPos.z = 0.0f;
//set autopilot
m_aAutopilotTargetAngle = 0;
m_vAutopilotTarget.x = 0.0f;
m_vAutopilotTarget.y = 0.5f;
m_vAutopilotTarget.z = 0.0f;
EngageAutopilot(true);
}
StepNavigation moves the solver one step and updates the camera:
void StepNavigation(float fElapsedTime)
{
//update autopilot position
DoAutopilot( fElapsedTime);
m_vCameraPos = GetCameraPos();
m_fCameraYaw = AngleToFloat(GetCameraYaw() );
//use autopilot position to update self camera
g_SelfCamera.SetYaw(m_fCameraYaw);
g_SelfCamera.SetEye(m_vCameraPos);
}
EngageAutopilot ensures we are within the maze (and snaps the camera inside if it isn’t already) as well as sets up the visited cell data structure and picks the autopilot target cell:
void EngageAutopilot(BOOL bEngage)
{
m_bEngageAutopilot = bEngage;
BOOL bPrevious = m_bAutopilot;
m_bAutopilot = bEngage;
// If we weren't on autopilot before and are on autopilot now
//then need to init autopilot
if( m_bAutopilot && !bPrevious )
{
// First of all, snap us to the centre of the current cell
int cellx = int(m_vCameraPos.x);
int cellz = int(m_vCameraPos.z);
m_vCameraPos.x = cellx + 0.5f;
m_vCameraPos.z = cellz + 0.5f;
// Ensure we're within the maze boundaries
if( cellx < x =" 0.5f;">= int(g_Maze.GetWidth()) )
m_vCameraPos.x = g_Maze.GetWidth() - 0.5f;
if( cellz < z =" 0.5f;">= int(g_Maze.GetHeight()) )
m_vCameraPos.z = g_Maze.GetHeight() - 0.5f;
// Clear the visited array and stack
(g_dwLevel == 3)? g_dwLevel=0:g_dwLevel++;
ZeroMemory( m_AutopilotVisited, sizeof(m_AutopilotVisited) );
m_AutopilotStack.Empty();
// Pick the next target cell
PickAutopilotTarget();
}
}
PickAutopilotTarget walks the visited cell data structure and selects the next target. It may need to execute a turn to do so, and Turning uses these definitions that have been lying dormant in CMaze.h waiting for us to catch up in the implementation:
#define NORTH_ANGLE 0x8000
#define EAST_ANGLE 0xc000
#define SOUTH_ANGLE 0x0000
#define WEST_ANGLE 0x4000
PickAutopilotTarget ensures we are within the maze (and snaps the camera inside if it isn’t already) as well as sets up the visited cell data structure and picks the autopilot target cell. The body of the implementation is:The body of the implementation is:
void PickAutopilotTarget()
{
// Get current cell and mark as visited
DWORD currentx = DWORD(m_vCameraPos.x);
DWORD currentz = DWORD(m_vCameraPos.z);
m_AutopilotVisited[currentz][currentx] = 1;
// Figure out which directions are allowed.
//We're allowed to go in any direction where
//there isn't a wall in the way and
//that takes us to a cell we've visited before.
BYTE cell = g_Maze.GetCellMaskXY(currentx,currentz);
ANGLE alloweddirs[5];
DWORD dwAllowed = 0;
if( !(cell & MAZE_WALL_NORTH) && !m_AutopilotVisited[currentz-1][currentx] )
alloweddirs[dwAllowed++] = NORTH_ANGLE;
if( !(cell & MAZE_WALL_WEST) && !m_AutopilotVisited[currentz][currentx-1] )
alloweddirs[dwAllowed++] = WEST_ANGLE;
if( !(cell & MAZE_WALL_EAST) && !m_AutopilotVisited[currentz][currentx+1] )
alloweddirs[dwAllowed++] = EAST_ANGLE;
if( !(cell & MAZE_WALL_SOUTH) && !m_AutopilotVisited[currentz+1][currentx] )
alloweddirs[dwAllowed++] = SOUTH_ANGLE;
// Is there anywhere to go?
if( dwAllowed == 0 )
{
// Nope. Can we backtrack?
if( m_AutopilotStack.GetCount() > 0 )
{
// Yes, so pop cell off the stack
AutopilotCell autoCell(m_AutopilotStack.Pop());
m_vAutopilotTarget.x = float(autoCell.x) + 0.5f;
m_vAutopilotTarget.z = float(autoCell.y) + 0.5f;
if( autoCell.x < m_aautopilottargetangle =" WEST_ANGLE;"> currentx )
m_aAutopilotTargetAngle = EAST_ANGLE;
else if( autoCell.y > currentz )
m_aAutopilotTargetAngle = SOUTH_ANGLE;
else
m_aAutopilotTargetAngle = NORTH_ANGLE;
}
else
{
// No, so we have explored entire maze and must start again
(g_dwLevel == 3)? g_dwLevel=0:g_dwLevel++;
ZeroMemory( m_AutopilotVisited, sizeof(m_AutopilotVisited) );
m_AutopilotStack.Empty();
//pick next cell target
PickAutopilotTarget();
}
}
else
{
// See if we can continue in current direction
BOOL bPossible = FALSE;
for( DWORD i = 0; i <>
{
if( alloweddirs[i] == m_aCameraYaw )
{
bPossible = TRUE;
break;
}
}
// If it's allowed to go forward,
// then have 1 in 2 chance of doing that anyway,
// otherwise pick randomly from available alternatives
if( bPossible && (rand() & 0x1000) )
m_aAutopilotTargetAngle = m_aCameraYaw;
else
m_aAutopilotTargetAngle = alloweddirs[ (rand() % (dwAllowed<<3)>>3 ];
m_vAutopilotTarget.z = float(currentz) + 0.5f;
m_vAutopilotTarget.x = float(currentx) + 0.5f;
switch( m_aAutopilotTargetAngle )
{
case SOUTH_ANGLE:
m_vAutopilotTarget.z += 1.0f;
break;
case WEST_ANGLE:
m_vAutopilotTarget.x -= 1.0f;
break;
case EAST_ANGLE:
m_vAutopilotTarget.x += 1.0f;
break;
case NORTH_ANGLE:
m_vAutopilotTarget.z -= 1.0f;
break;
}
// Push current cell onto stack
m_AutopilotStack.Push( AutopilotCell(BYTE(currentx),BYTE(currentz)) );
}
}
m_vAutopilotTarget.z = float(currentz) + 0.5f;
m_vAutopilotTarget.x = float(currentx) + 0.5f;
switch( m_aAutopilotTargetAngle )
{
case SOUTH_ANGLE:
m_vAutopilotTarget.z += 1.0f;
break;
case WEST_ANGLE:
m_vAutopilotTarget.x -= 1.0f;
break;
case EAST_ANGLE:
m_vAutopilotTarget.x += 1.0f;
break;
case NORTH_ANGLE:
m_vAutopilotTarget.z -= 1.0f;
break;
}
// Push current cell onto stack
m_AutopilotStack.Push( AutopilotCell(BYTE(currentx),BYTE(currentz)) );
}
}
DoAutopilot walks down a block of cells until the target cell is reached, marking cells as it goes:
void DoAutopilot(FLOAT fElapsed)
{
DWORD Width, Height;
Width = g_Maze.GetWidth();
Height = g_Maze.GetHeight();
// While there is still time to use up...
while( fElapsed )
{
// Initialize velocities
m_fCameraVelPos = 0.0f;
m_nCameraVelYaw = 0;
// See if we need to turn
if( m_aAutopilotTargetAngle != m_aCameraYaw )
{
SHORT diff = SHORT((m_aAutopilotTargetAngle - m_aCameraYaw) &
TRIG_ANGLE_MASK);
FLOAT fNeeded = abs(diff)/40.0f;
if( fNeeded/1000.0f <= fElapsed )
{
m_aCameraYaw = m_aAutopilotTargetAngle;
fElapsed -= fNeeded/1000.0f;
}
}
else
{
if( diff <>
{
m_aCameraYaw -= (DWORD) ((fElapsed*1000.0f) * 40.0f);
m_nCameraVelYaw = -40000; // Constant auto pilot rate
}
else
{
m_aCameraYaw += (DWORD) ((fElapsed*1000.0f) * 40.0f);
m_nCameraVelYaw = 40000; // Constant auto pilot rate
}
fElapsed = 0;
}
}
else
{
// Ensure vAutopilotTarget is inside the maze boundry
if( m_vAutopilotTarget.x <>= Width
m_vAutopilotTarget.z <>= Height )
{
//reset and restart
(g_dwLevel == 3)? g_dwLevel=0:g_dwLevel++;
ZeroMemory( m_AutopilotVisited, sizeof(m_AutopilotVisited) );
m_AutopilotStack.Empty();
PickAutopilotTarget();
return;
}
// Facing right way, so now compute distance to target
D3DXVECTOR3 diff = m_vAutopilotTarget - m_vCameraPos;
float fRange = float(sqrt((diff.x*diff.x)+(diff.z*diff.z)));
// Are we there yet?
if( fRange > 0 )
{
// No, so compute how long we'd need
FLOAT fNeeded = fRange / 0.002f;
//Ensure we never leave the boundary of the Maze.
D3DXVECTOR3 pos = m_vCameraPos;
// Do we have enough time this frame?
if( fNeeded/1000.0f <= fElapsed )
m_vAutopilotTarget.z <>= Height )
{
//reset and restart
(g_dwLevel == 3)? g_dwLevel=0:g_dwLevel++;
ZeroMemory( m_AutopilotVisited, sizeof(m_AutopilotVisited) );
m_AutopilotStack.Empty();
PickAutopilotTarget();
return;
}
// Facing right way, so now compute distance to target
D3DXVECTOR3 diff = m_vAutopilotTarget - m_vCameraPos;
float fRange = float(sqrt((diff.x*diff.x)+(diff.z*diff.z)));
// Are we there yet?
if( fRange > 0 )
{
// No, so compute how long we'd need
FLOAT fNeeded = fRange / 0.002f;
//Ensure we never leave the boundary of the Maze.
D3DXVECTOR3 pos = m_vCameraPos;
// Do we have enough time this frame?
if( fNeeded/1000.0f <= fElapsed )
{
// Yes, so just snap us there
pos.x = m_vAutopilotTarget.x;
pos.z = m_vAutopilotTarget.z;
fElapsed -= fNeeded/1000.0f;
}
else
{
// No, so move us as far as we can
pos.x -= Sin(m_aCameraYaw) * 0.002f * fElapsed*1000.0f;
pos.z += Cos(m_aCameraYaw) * 0.002f * fElapsed*1000.0f;
m_fCameraVelPos = 2.0f; // Velocity constant
fElapsed = 0;
}
// Ensure that we have stayed within the maze boundaries
if( pos.x < x =" 0.1f;">
if( pos.x >= Width ) pos.x = Width - 0.1f;
if( pos.z < z =" 0.1f;">
if( pos.z < z =" 0.1f;">
if( pos.z >= Height ) pos.z = Height - 0.1f;
// Assign our new values back to our globals.
m_vCameraPos = pos;
}
else
{
// Reached target, so pick another
PickAutopilotTarget();
}
}
}
}
Callback changes
// Assign our new values back to our globals.
m_vCameraPos = pos;
}
else
{
// Reached target, so pick another
PickAutopilotTarget();
}
}
}
}
Callback changes
Now that we can control navigation through the maze, we need to add the code to do so. This comes in 2 parts: starting up the navigation, stepping the navigation.
For starting up, CreateDevice is the place to add the call to StartNavigation. Here is the D3D10 code:
HRESULT CALLBACK OnD3D10CreateDevice( ID3D10Device* pd3dDevice, const DXGI_SURFACE_DESC* pBackBufferSurfaceDesc,
void* pUserContext )
{
…
hr = g_MazeSim.Init10(g_dwRandomSeed,pd3dDevice);
StartNavigation();
return S_OK;
}
And here is the D3D9 code:
HRESULT CALLBACK OnD3D9CreateDevice( IDirect3DDevice9* pd3dDevice, const D3DSURFACE_DESC* pBackBufferSurfaceDesc,
void* pUserContext )
{
…
hr = g_MazeSim.Init9(g_dwRandomSeed,pd3dDevice);
StartNavigation();
return S_OK;
}
Yes, it really is that simple, just add the call after the maze is created and initialized.
For stepping, FrameMove is the place to add the call to StepNavigation:
void CALLBACK OnFrameMove( double fTime, float fElapsedTime, void* pUserContext )
{
if ( g_bRunSim )
{
//update the solved position
StepNavigation(fElapsedTime);
//update the self camera's position based on the sim input
g_SelfCamera.FrameMove( fElapsedTime );
}
// Update the sky camera's position based on user input
g_SkyCamera.FrameMove( fElapsedTime );
}
{
if ( g_bRunSim )
{
//update the solved position
StepNavigation(fElapsedTime);
//update the self camera's position based on the sim input
g_SelfCamera.FrameMove( fElapsedTime );
}
// Update the sky camera's position based on user input
g_SkyCamera.FrameMove( fElapsedTime );
}
We do that only when the sim is active and not paused. Note, the sky camera is enabled all the time, but the maze camera is only enabled when the sim is active. Remember that, as when we add better camera control that detail will surface again.
No other callback changes are required. Sweet!
Conclusion
Now we are starting to get somewhere. Not only do we have rendering the maze, we have behaviors with the navigation.
Here are 2 screenshots:
D3D10 turning during navigation
D3D9 turning during navigation
Here is a link to the project with full source.
Here is a link to a Word document for better formatting.
Next up in the series are:
· better camera control,
· an animated character rendered at the solver location,
· additional maze rendering features, and
· generating a new maze when the current one is full solved.
I am still working on the code for maze goals, so when I get that complete I will add it to the series.
Posts