Pathfinder using DirectX and Genetic Algorithms
Well, I've been threatening it for long enough, now it's time for some action : ) Over the course of the next few weeks I'll aim to build a simple 2D application that demonstrates how a Pathfinder application can be developed using genetic algorithm's. I'm going to use DirectX to render the 2D display because I've been messing about with it on and off for a while now and happen to think it's really cool. I'll aim to walk you through the code (of which there will be quite a bit) and so this example will be comprised of multiple parts, each covering a logical step in the example build.
This first step then will take you through creating the initial C++ application, registering and creating the standard window's bits (entry point, window, message loop, callback proc etc etc) and setting up and initialising DirectX, ready for use. I guess I'm hoping that even if you've never used C++ or DirectX before you'll find these instructions easy enough to at least follow, if not fully understand.
And with that, let's begin. The first thing to do is to make sure you have the latest DirectX SDK installed (currently DirectX 10), you can find this by browsing here. I'm assuming you have Visual Studio installed also. Kick off by creating a new C++ project using the 'empty project' template. As its name implies, this does nothing more than create a base project with nothing in it, a blank canvas if you will.
Next, you need to add a .cpp to the Source Files directory to enable you to write your code, call it whatever you want - entry_point.cpp will do nicely and hey presto, you're ready to rock and roll. At this point I should add a bit of a disclaimer regarding the code I write - please don't consider it a shining example of best practice in any areas, it's simply sample code that demonstrates a number of concepts, nothing more. It's not layed out nicely or anything either, you've been warned.
Strap yourselves in, it's time to code. In this first step, we need to define an entry point for our application, from which everything else will follow. When writing a Windows application in C++, there are a number of different entry point methods that can be used. In our case, we're going to write a Windows application that may cater for Unicode support, and so we're going to use the _tWinMain entry point method. Under the covers, this generic entry point method will actually call either WinMain (non unicode support) or wWinMain (Unicode support) depending on whether the _UNICODE compiler flag has been defined.
int
APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{}
As you can see, this function returns data of type integer and has four parameters that are set for you when the application is loaded and started. The first parameter, hInstance is the instance handle for the current application. The next parameter, hPrevInstance will always be set to NULL in a Win32 application, and was used to identify an instance of the application already running in a 16-bit Windows application. Next up is lpCmdLine, which is a pointer to a null-terminated string containing the command line used to fire up the application. Finally you have nCmdShow, which can be one of a number of values that determines how the window itself will be shown.
Let's take a look at the contents of this function.
int
APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{
if (!InitialiseWindow(hInstance))
{
return FALSE;
}
MSG msg = {0};
while (WM_QUIT != msg.message)
{
while (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE) == TRUE)
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
return (int) msg.wParam;
}
The first thing to note is that a function called InitialiseWindow is called. This is a function you're going to write that you'll see shortly, and its job will be to define, register and show the application window. Next comes the important part, the message loop. This is the top level controller for your application, and its task is a simple one, to retrieve and send messages that are on the thread message queue. To do this, the PeekMessage function is used to check the queue and extract the message information (if any). Five parameters are required. The first is the address of the MSG structure to populate. The second is a handle to a window whose messages you're checking, NULL signifies the current window. The third and fourth parameters are min and max values that allow you to specify a range of messages that should be checked. Finally, you specify whether or not messages should be removed after being processed.
If you look at some examples online, you'll often see GetMessage used in place of PeekMessage. GetMessage is a blocking call however and won't return until a message is received, no good for a game or suchlike.
Within the message loop are two function calls, TranslateMessage and DispatchMessage. TranslateMessage translates virtual-key codes into character messages and DispatchMessage sends the message to a windows procedure (which you'll see soon). That's pretty much it for this method for the time being, let's turn our attention now to the business of actually creating and showing our application window via the InitialiseWindow function.
bool
InitialiseWindow(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
ZeroMemory(&wcex, sizeof(WNDCLASSEX));
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = (WNDPROC)WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = 0;
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
wcex.lpszMenuName = NULL;
wcex.lpszClassName = TEXT("DirectXAITutorialClass");
wcex.hIconSm = 0;
RegisterClassEx(&wcex);
RECT rect = { 0, 0, SCREEN_WIDTH, SCREEN_HEIGHT };
AdjustWindowRect(&rect, WS_OVERLAPPEDWINDOW, FALSE);
g_hWnd = CreateWindowEx(NULL,
TEXT(
"DirectXAITutorialClass"),
TEXT("DirectXAITutorial"),
WS_OVERLAPPEDWINDOW,
300,
300,
rect.right - rect.left,
rect.bottom - rect.top,
NULL,
NULL,
hInstance,
NULL);
if(!g_hWnd)
{
return FALSE;
}
ShowWindow(g_hWnd, SW_SHOW);
UpdateWindow(g_hWnd);
return TRUE;
}
Yes I know, looks like a lot of work to show a window, there's really nothing to it though (please check the msdn documentation for a breakdown of all the parameters). There are a few basic steps that need to be followed in order to show a window. First, a window class needs to be defined and information such as cursor type, background color, icon and style provided. The WNDCLASSEX structure is used to hold this information. One of the key parameters in this definition is lpfnWndProc, which expects a function pointer to a procedure that will handle messages, you'll see this in a little while. Once this definition is complete, it needs to be registered with the system so it can then be used. The RegisterClassEx function is used to perform this task.
Next, the CreateWindowEx function is called and its job is to actually create an instance of the window that we defined earlier and return a handle to this instance. Again, please check the documentation for a listing of all the parameters, but the starting position, size, window class and text are all specified here.
All that remains at this point is to actually show the window via a call to ShowWindow. You can see also that UpdateWindow is called after this, which sends a WM_PAINT message to the window, effectively getting it to redraw itself.
Voila.
Almost there. We now need to implement a function whose job it is to actually do something with messages for our window, this is the function we specified in the WNDCLASSEX function.
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
switch(message)
{
case WM_DESTROY:
{
PostQuitMessage(0);
return 0;
}
break;
}
return DefWindowProc(hWnd, message, wParam, lParam);
}
This function contains a switch construct that is used to define what should happen for different messages. At the moment only one type of message is checked for - WM_DESTROY - which is sent to the window when it is being destroyed. When this message is received, PostQuitMessage is called which places a WM_QUIT message in the thread message queue, indicating to the system that the thread has made a request to terminate.
Finally, DefWindowProc should always be called as this function provides default message processing for any messages that the application does not specifically process.
In terms of putting together a blank Windows application, we're done. The full code listing is now shown, try copying it into your source file and compile and run it. A blank window should appear. There's a few lines of code I've added that allows you to exit the application by hitting the escape key, and of course the standard header gubbins and prototyping.
#include
<windows.h>
#include <tchar.h>
HWND hWnd;
#define
KEY_DOWN(vk_code) ((GetAsyncKeyState(vk_code) & 0x8000) ? 1 : 0)
#define KEY_UP(vk_code) ((GetAsyncKeyState(vk_code) & 0x8000) ? 0 : 1)
const
int SCREEN_WIDTH = 640;
const int SCREEN_HEIGHT = 480;
bool
InitialiseWindow(HINSTANCE hInstance);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
int
APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{
if (!InitialiseWindow(hInstance))
{
return false;
}
MSG msg = {0};
while (WM_QUIT != msg.message)
{
while (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE) == TRUE)
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
if(KEY_DOWN(VK_ESCAPE))
PostMessage(hWnd, WM_DESTROY, 0, 0);
}
return (int) msg.wParam;
}
bool
InitialiseWindow(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
ZeroMemory(&wcex, sizeof(WNDCLASSEX));
wcex.cbSize =
sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = (WNDPROC)WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = 0;
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
wcex.lpszMenuName = NULL;
wcex.lpszClassName = TEXT("DirectXAITutorialClass");
wcex.hIconSm = 0;
RegisterClassEx(&wcex);
RECT rect = { 0, 0, SCREEN_WIDTH, SCREEN_HEIGHT };
AdjustWindowRect(&rect, WS_OVERLAPPEDWINDOW, FALSE);
hWnd = CreateWindowEx(NULL,
TEXT(
"DirectXAITutorialClass"),
TEXT("DirectXAITutorial"),
WS_OVERLAPPEDWINDOW,
300,
300,
rect.right - rect.left,
rect.bottom - rect.top,
NULL,
NULL,
hInstance,
NULL);
if(!hWnd)
{
return false;
}
ShowWindow(hWnd, SW_SHOW);
UpdateWindow(hWnd);
return true;
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
switch(message)
{
case WM_DESTROY:
{
PostQuitMessage(0);
return 0;
}
break;
}
return DefWindowProc(hWnd, message, wParam, lParam);
}
Now we've got that bit out of the way it's time to turn our attention to something more interesting, DirectX. DirectX is a high performance API for rendering graphics to screen, utilising the video card directly. It's based on COM and you can program against it in the managed environment now also. This is the technology we're going to use to render our 2D graphics, so let's get cracking. First off, there's a couple of extra include directives needed to use DirectX 10.
#include
<d3d10.h>
#include <d3dx10.h>
And you also need to make sure you link to the DirectX .lib file, you can do this from the Project Properties pane accessed by right-clicking the project name in Solution Explorer.
There's a few global variables we're going to set up for ease of use also.
ID3D10Device* g_pD3DDevice = NULL;
IDXGISwapChain* g_pSwapChain = NULL;
ID3D10RenderTargetView* g_pRenderTargetView = NULL;
The first one, ID3D10Device is a device interface used to perform rendering and to create a number of different resources such as Textures. Consider it a virtual adapter for Direct3D 10. IDXGISwapChain represents a collection of 'surfaces' that can be drawn to before being displayed on screen, usually 2 but sometimes more. The Swap Chain is used to implement buffering, allowing rendering to occur on the buffer that is not currently being displayed and, once rendering is complete the buffers are swapped around and the finished rendering is drawn on the monitor display. Without buffering, flickering and image tearing will occur as the monitor refreshes partway through drawing to the currently active buffer (surface). Finally, ID3D10RenderTargetView allows us to bind the back buffer in our Swap Chain as the render target.
Next, we're going to write a function called InitialiseDirectX10 that will, you guessed it, perform the initialisation and setup of the DirectX 10 components.
bool
InitialiseDirectX10()
{
DXGI_SWAP_CHAIN_DESC sd;
ZeroMemory(&sd, sizeof(sd));
sd.BufferCount = 1;
sd.BufferDesc.Width = SCREEN_WIDTH;
sd.BufferDesc.Height = SCREEN_HEIGHT;
sd.BufferDesc.Format = DXGI_FORMAT_R8G8B8A8_UNORM;
sd.BufferDesc.RefreshRate.Numerator = 60;
sd.BufferDesc.RefreshRate.Denominator = 1;
sd.BufferUsage = DXGI_USAGE_RENDER_TARGET_OUTPUT;
sd.OutputWindow = g_hWnd;
sd.SampleDesc.Count = 1;
sd.SampleDesc.Quality = 0;
sd.Windowed = TRUE;
HRESULT hr = D3D10CreateDeviceAndSwapChain(NULL,
D3D10_DRIVER_TYPE_HARDWARE,
NULL,
0,
D3D10_SDK_VERSION,
&sd,
&g_pSwapChain,
&g_pD3DDevice);
if (FAILED(hr))
{
MessageBox(g_hWnd, TEXT("Error Message Here"), TEXT("ERROR"), MB_OK);
return FALSE;
}
ID3D10Texture2D* pBackBuffer;
hr = g_pSwapChain->GetBuffer(0,
__uuidof(ID3D10Texture2D), (LPVOID*)&pBackBuffer);
if (FAILED(hr))
{
return FALSE;
}
hr = g_pD3DDevice->CreateRenderTargetView(pBackBuffer, NULL, &g_pRenderTargetView);
pBackBuffer->Release();
if (FAILED(hr))
{
return FALSE;
}
g_pD3DDevice->OMSetRenderTargets(1, &g_pRenderTargetView, NULL);
D3D10_VIEWPORT viewPort;
viewPort.Width = SCREEN_WIDTH;
viewPort.Height = SCREEN_HEIGHT;
viewPort.MinDepth = 0.0f;
viewPort.MaxDepth = 1.0f;
viewPort.TopLeftX = 0;
viewPort.TopLeftY = 0;
g_pD3DDevice->RSSetViewports(1, &viewPort);
return true;
}
Again, looks like an awful lot is going on here but it's really rather simple. The first thing we need to do is to create both our DirectX device and our swap chain. To do this, we make a call to the D3D10CreateDeviceAndSwapChain function, passing in a DXGI_SWAP_CHAIN_DESC structure that describes in detail what type of Swap Chain we want to create. We also pass in the address of our device and swap chain pointers to populate and that's it. For a full explanation of all the parameters please consult the documentation here.
Next, we need to get a handle to the buffer that we're going to render to and then set this as our render target, before setting up a default view port to view the entire render scene from. Again, there isn't much point in me duplicating in depth information about method calls and parameters that are readily available in the documentation shipped with the SDK.
Finally for this first part of the tutorial, you need to add a function which will be responsible for cleaning up the DirectX objects that you've created and a function responsible for actually rendering the scene, these are listed below.
void
RenderFrame()
{
if (g_pD3DDevice != NULL)
{
g_pD3DDevice->ClearRenderTargetView(g_pRenderTargetView, D3DXCOLOR(0.0f, 0.0f, 0.0f, 0.0f));
g_pSwapChain->Present(0, 0);
}
}
void
ClearUpD3D10()
{
if (g_pRenderTargetView)
g_pRenderTargetView->Release();
if (g_pSwapChain)
g_pSwapChain->Release();
if (g_pD3DDevice)
g_pD3DDevice->Release();
}
The clean up function doesn't require any explanation, we just release the COM objects that have been created so far. For the render function, it's about the simplest render that can be performed, painting the screen a single colour using the ClearRenderTargetView command. Following this Present is called, which takes care of taking the back buffer that's been rendered to and displaying it on screen.
The entry point method will of course need altering to make use of these new functions.
int
APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{
if (!InitialiseWindow(hInstance))
{
return FALSE;
}
if (!InitialiseDirectX10())
{
return FALSE;
}
MSG msg = {0};
while (WM_QUIT != msg.message)
{
while (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE) == TRUE)
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
if(KEY_DOWN(VK_ESCAPE))
PostMessage(g_hWnd, WM_DESTROY, 0, 0);
RenderFrame();
}
ClearUpD3D10();
return (int) msg.wParam;
}
If you compile and run your program you should be presented with a window painted with a single colour.
In Part 2, we'll look at drawing the scene we're going to use for this example as well as start looking at the genetic algorithm implementation.