At the forefront of Artificial Intelligence

Home » Articles » Programming » A* Explorer

A* Explorer Tutorial (Part I)

This tutorial is aimed at helping people develop their own plugins for A* Explorer. As of version 2.0, the plugin scheme is not definite, but the specifications will definitely not change so radically it will warrant a complete rewrite of anything you develop.

This tutorial will step through the tutorial01.dll that comes with A* Explorer adding a "Water feature" to A* Explorer, therefore will be step through the code bit by bit. Firstly, just note that (for the moment) A* Explorer extensions must be MFC DLLs if they are to support custom drawing (which tutorial01.dll does). Therefore, there is a little redundant code about, but this is a small price to pay. For our purposes though, all the pertinent code is in AseExports.cpp.

The A* Functions

Firstly, let us look at the A* functions (note: all the code to this is available with the A* Explorer download). These are AseValid, AseCost and AseDistance. These are the functions that are called by the main A* engine. We'll jump straight into the first function to get an idea about what is going on:

ASEAPI int AseValid(_asNode *pParent, _asNode *pNode, int iData, void *pPointer)
{
	int x = pNode->x, y = pNode->y;

	if (x < 0 || y < 0 || x >= g_iDimX || y >= g_iDimY) return FALSE;

	UCHAR cTerrain = g_pBoard[CI(x,y)];
	UCHAR cWater   = g_pWater[CI(x,y)];
	
	// Impassable (ignore impassable w/water over it)
	if (cTerrain == 0 && cWater == 0) return FALSE;

	// Water is too deep.
	if (g_pWater[CI(x, y)] > 128) return FALSE;

	// Cannot transverse steep terrain (although water takes priority)
	if (fabs(g_pBoard[CI(pParent->x, pParent->y)] - cTerrain) > 128 && cWater == 0) 
		return FALSE;

	return TRUE;
}

Firstly, we ensure that the x and y coordinates are within the boundaries of the map. Next we grab the terrain and water information. Note that the water information is stored in the DLL itself, whereas the terrain information has been received from A* Explorer.

So, if the terrain is impassable (0) and there is no water covering it (in which case it may be passable) then return FALSE. Next we check to see if the water is too deep to cross (greater than 128), and finally we do a more advanced check to see if the change we're looking at is steep (the parent's height value - the current node's height value is greater than 128). If it is too steep, we return, but only if it isn't covered in water (because, again, it might be passable).

AseCost and AseDistance deal with water in much the same way.

AseMessage

This is where things can get a little complicated. AseMessage is an all-encompassing message handler that will deal with everything from registering the DLL to saving and loading and mouse clicks to drawing! We'll take the function a message at a time.

ASEAPI ASERESULT AseMessage(ASEMSG uMessage, ASEPARAM wParam, ASEPARAM lParam)
{
	// AseMessage can handle a mixture of Windows and Ase-specific messages.

	switch (uMessage) {
		case ASE_INITIALIZE: {
			return TRUE;
		}

This is the initialization message. Since no initialization is required, we just return TRUE to signal everything is fine.

		case ASE_DESTROY: {
			return Destroy();
		}

This is the destruction message. Our destroy function merely deallocates any memory we allocated earlier on. Again, we return TRUE if everything succeeded.

		case ASE_REGISTER: {
			return (ASERESULT)AseRegister((UINT *)wParam);
		}

This is our registration message. This function tells A* Explorer how many custom buttons are required and what bitmaps/brushes to use. we will cover registration a little further down.

		case ASE_SETBOARDINFO: {
			LPBOARDINFO lpBoardInfo = (LPBOARDINFO)lParam;

			g_iDimX = lpBoardInfo->uDimX;
			g_iDimY = lpBoardInfo->uDimY;
			g_pBoard = lpBoardInfo->pData;
			g_iGrid  = lpBoardInfo->uGridSize;

			if (g_pWater) Destroy();

			g_pWater = new UCHAR[g_iDimX * g_iDimY];
			memset(g_pWater, 0, g_iDimX * g_iDimY);

			break;
		}

ASE_SETBOARDINFO passes the extension all the necessary information about the map it will be working on as well as some simple display information (grid size). Therefore, for purposes of our extension, we retrieve the information then allocate the necessary space for our water, since we want it the same size as our main board.

		case ASE_DESCRIPTION: {
			LPASEDESCRIPTION lpDescription = (LPASEDESCRIPTION)lParam;
			
			lpDescription->bHasProperties = FALSE;

			_tcscpy(lpDescription->szName, "A* Explorer Tutorial 01");
			_tcscpy(lpDescription->szDescription, "...");

			break;
		}

This is fairly self-explanatory. The ASE_DESCRIPTION message supplies descriptive information for the DLL Extension dialog box. The bHasProperties denotes whether the extension has a property box or not.

		case ASE_WSERIALIZE: {
			UINT  *piBytes = (UINT *)wParam;

			*piBytes = g_iDimX * g_iDimY;

			return (ASERESULT)g_pWater;
		}

		case ASE_RSERIALIZE: {
			ASSERT(wParam == g_iDimX * g_iDimY);

			memcpy(g_pWater, (const void *)lParam, g_iDimX * g_iDimY);
			
			break;
		}

These are the write (ASE_WSERIALIZE) and read (ASE_RSERIALIZE) functions. When writing, the extension must pass back two pieces of information. The data to write and the number of bytes required. The number of bytes is put into the wParam of the message, while a pointer to the data is returned.

When reading, wParam denotes the number of bytes being passed to the extension, while the lParam is a pointer to the data.

		case ASE_VALID: {
			// Ensure nodes can't be placed where they are unreachable.
			if (g_pWater[CI(wParam, lParam)] > 128) return ASE_POSINVALID;	

			return ASE_POSVALID;
		}

Dot not get AseValid (the function) and the ASE_VALID (message) confused. AseValid is used by the A* algorithm to determine if a particular node is valid for transversal. ASE_VALID is called when placing start and end nodes during map drawing (and before the A* is run). You can see how it is used in this extension to ensure that start/end nodes aren't placed in "deep" water.

		case WM_LBUTTONDOWN: {
			LPASECLICK pMsg = (LPASECLICK)(lParam);
			
			Click(pMsg);
			g_bDragging = TRUE;
			break;
		}

		case WM_MOUSEMOVE: {
			LPASECLICK pMsg = (LPASECLICK)(lParam);

			if (g_bDragging) Click(pMsg);

			break;
		}

		case WM_LBUTTONUP: {
			g_bDragging = FALSE;
			break;
		}

These three functions are simple Windows WM_ messages that are passed on to the extension. The water extension uses it to allow the user to drag water, or move over the same area to make the water deeper. Since this isn't directly related to extension development, I'll leave it up to you to look at the code.

		case WM_PAINT:
		case ASE_PAINT: {
			return DrawWater((CDC *)lParam);
		}

		default: return ASE_NOTHANDLED;
	}

	return 0;
}

Similarly, the rest is quite simple. The ASE_PAINT function tells the extension to draw the water on the DC it has been passed. Important: Having the default handler return ASE_NOTHANDLED is quite important since future features may rely on this to ensure correct operation.

Registration

We jumping back to registration now to see how the extensions are registered with the main program. The way registration works is fairly straightforward. The ASE_REGISTER sets lParam to the number of custom brushes, and returns a pointer to the registration information. This is what AseRegister does (on behalf of ASE_REGISTER):

static ASEREGISTER g_RegisterInfo[] = {
	{ ASE_USERBRUSH + 0, IDB_WATER },
	{ ASE_USERBRUSH + 1, IDB_GROUND },
};

ASEREGISTER *AseRegister(UINT *iNumCustom)
{
	// ...
	
	*iNumCustom = sizeof(g_RegisterInfo) / sizeof(ASEREGISTER);

	return &g_RegisterInfo[0];
}

The registration information is simple - it consists of two constants. One denotes the brush to use, this is normally ASE_USERBRUSH + x as shown. The next the name of the bitmap to use as the button. IDB_WATER and IDB_GROUND are two bitmaps defined in the resource section of the DLL.

Conclusion

tutorial01.dll is not a simple extension since it has custom drawing and mouse control as well as custom heuristics. Therefore, if you understand this tutorial, you are well on your way to creating some cool additions to A* Explorer! If all the drawing and mouse tracking is too much, start by simply creating your own custom heuristics.

Submitted: 30/08/2002

Article Toolbar

BibTeX entry