Saturday, February 21, 2009

Maze Sample : Article 5 - D3D10Maze-Solve

Our next article is about solving the maze.

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:


D3D9


D3D10

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;
}
}

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)) );
}
}

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 )
{
// 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 >= 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

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 );
}

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.

Thursday, February 12, 2009

Larrabee at GDC 2009 and Intel 2009 roadmap

Larrabee update at GDC:

For complete details see:
http://software.intel.com/en-us/articles/intel-at-gdc/

2 sessions on the Larrabee new instruction set, LRBni:

Rasterization on Larrabee: A First Look at the Larrabee New Instructions (LRBni) in Action
https://www.cmpevents.com/GD09/a.asp?option=C&V=11&SessID=9138
by Mike Abrash

and

SIMD Programming with Larrabee: A Second Look at the Larrabee New Instructions (LRBni) in Action
https://www.cmpevents.com/GD09/a.asp?option=C&V=11&SessID=9139
by Tom Forsyth

And a session on our new performance tool:

Graphics Performance Tools Today, for Tomorrow's Visuals
https://www.cmpevents.com/GD09/a.asp?option=C&V=11&SessID=9262

Should be at the top of everyone's list.

Note, it is pretty rare for Intel to disclose instruction sets this early.

Intel 2009 Roadmap Update:

At Ars Technica:
http://arstechnica.com/hardware/news/2009/02/intel-talks-2009-its-32nm-full-speed-ahead.ars

At FiringSquad:
http://firingsquad.com/hardware/intel_32nm_westmere_roadmap/

Thats plenty of reading material.

Tuesday, February 10, 2009

End of an Era Part III: More Updates

The layoff of Aces is definitely the news that doesn't want to quit.

More news reports
http://www.pcworld.com/article/158274/microsoft_layoffs.html?tk=rss_news
http://www.theregister.co.uk/2009/02/03/microsoft_flight_simulator_partners/

Letter to Steve Ballmer and reply by Pat
http://forums.flightsim.com/vbfs/showthread.php?t=192725

Notice on the BBC about this
http://news.bbc.co.uk/1/hi/technology/7874937.stm

Letter to Phil Spencer
http://www.sim-outhouse.com/sohforums/showthread.php?t=10310

A petition site to show support
http://www.supportflightsim.com/

Facebook site to gain 100,000 fans


Avsim.com front page notice, reposted in the forums
http://forums1.avsim.net/index.php?showtopic=243303

That's Atlantic Monthly, Computer World, PC World, BBC. And probably more I haven't linked directly. Pretty mainstream. You don't last that long as a product without a dedicated following. And the fact that the product lasted that long means something in and of itself, an intangible.

So what does it all mean Alfie? I can tell you what I know, and I can then present some informed speculation.

There are 2 new groups being formed under 2 of the 5 top-level studio managers. No names, even though I know them. :-)

Group 1 is over in MS Research, with something like 20 heads this year and 10 transfer heads either this year or next fiscal year. The charter from my information is a bit vague but it sounds more like social networking 'stuff' using the character animation bits that Train Sim2 was going to have and that ESP2 was going to leverage. I wish them good luck.

Group 2 is in MGS and is of more interest to FS fans. The charter of this group is again not completely clear, but it is centered around a flying game. So the public responses from MS have a backing in reality. No, it does not sound like a "magical restart" of FS11 to me yet; but yes it is flight oriented. Exactly what it is we will not know until MGS tells us more. In terms of resources, Group 2 has something like 30 heads this year, and potentially 15 heads next fiscal year. And yes, in my opinion 45 heads is enough to do a credible job.

Yes, the job opening for an Art Lead that various folk have posted and commented about is in Group 2. However, I didn't see a lot of other job openings. That leads me to believe that specific job listing is tailored to enable hiring a specific individual, perhaps one with past history on the team. And the other heads will be filled from the talent pool of the former studio hence lack of other openings.

So thats what I know. Now its speculation time.

My opinion is that this is a serious change in the hobby. No one should doubt that. Anyone who tries to play this lightly is just fooling themselves.

With that said, the resolution of where FS is going in the future is not clear yet and will only play out over time. Until MGS actually states what the parameters of this new "flying game" are, it is impossible to tell how different from the deep simulation known as the FS series "the new thing" will be.

It could be great, so lets remember that. Plus, given FSX clearly has years of life in it, there is no need to see this as a 'chicken little' event yet. In that vein, I do think its fair that the community should give the new team, given it is going to be largely ex-Aces, a chance before weighing in with a judgment. I know these people and they truly care about the product and the community and will be committed to doing a great job.

And even if, according to some peoples' worst-case fears, the "new flying game" turns out to be a "play for pay" Windows Live experience that does not provide the full-planet experience and deep flight simulation that the community wants - would that mean the death of the hobby? No, some other provider would likely step in and fill the void if MS leaves such a large gap.

So my best suggestion is that for the immediate future people stop thrashing and have fun. There is plenty of flying to be done on FSX, and plenty of high-quality add-ons are queued up for your enjoyment. Go back to flying and stay tuned for future announcements from MGS and let's all agree to "wait and see what happens".

With that in mind, I also think its worth stating that until we get clearer data the community should try to avoid random speculation, acting rashly, and savaging each other on the forums. That surely has no real benefit to the community.

I'll avoid singing kumbaya and asking for a group hug now. :-)

Friday, February 6, 2009

Everyone saw this, right?

TheInquirer had a very interesting "leak" from Sony here.

I can neither confirm nor deny its true, because I am not privy to that compartment of information. But obviously that would make Larrabee even more interesting to developers. That and our volume predictions. :-).

EDIT: Sony issued the predictable denial here. We'll just have to wait and see who wins what. With some discussions talking about 4th gen consoles in 2012, we might have to wait a bit for confirmed news