I didn’t write this one, 100% of the credit goes to Daniel Strigl. The original article can be found at the code project here. It uses the Win32 API to achieve high performance timing and is wrapped really nicely in an easy to use class.
using System;
using System.Runtime.InteropServices;
using System.ComponentModel;
using System.Threading;
namespace Win32
{
internal class HiPerfTimer
{
[DllImport("Kernel32.dll")]
private static extern bool QueryPerformanceCounter(
out long lpPerformanceCount);
[DllImport("Kernel32.dll")]
private static extern bool QueryPerformanceFrequency(
out long lpFrequency);
private long startTime, stopTime;
private long freq;
// Constructor
public HiPerfTimer()
{
startTime = 0;
stopTime = 0;
if (QueryPerformanceFrequency(out freq) == false)
{
// high-performance counter not supported
throw new Win32Exception();
}
}
// Start the timer
public void Start()
{
// lets do the waiting threads there work
Thread.Sleep(0);
QueryPerformanceCounter(out startTime);
}
// Stop the timer
public void Stop()
{
QueryPerformanceCounter(out stopTime);
}
// Returns the duration of the timer (in seconds)
public double Duration
{
get
{
return (double)(stopTime - startTime) / (double) freq;
}
}
}
}
Wrote this little package to benchmark sections of code in Ada. You can adjust the level of detail by varying the number of digits passed into the Value string in the Stop() procedure – just be sure you passed in a string large enough to hold them all. It’s technically not a “high-performance” timer though, but in testing it seemed to work well for resolutions around 100th and 1000th of a second.
WITH Calendar;
PACKAGE Simple_Timer IS
PROCEDURE Start;
PROCEDURE Stop( Value : OUT String );
END Simple_Timer;
PACKAGE BODY Simple_Timer IS
Was : Standard.Duration;
Now : Standard.Duration;
PACKAGE Time_IO IS NEW Text_IO.Fixed_IO ( Standard.Duration );
PROCEDURE Start IS
BEGIN
Was := Calendar.Seconds( Calendar.Clock );
END Start;
PROCEDURE Stop( Value : OUT String ) IS
BEGIN
Now := Calendar.Seconds( Calendar.Clock ) - Was;
Time_IO.Put( Value, Now, Aft => 5, Exp => 0 );
END Stop;
BEGIN
Was := Calendar.Seconds( Calendar.Clock );
Now := Calendar.Seconds( Calendar.Clock ) - Was;
END Simple_Timer;
My senior project group is writing a game, and I’m the one doing all the AI algorithms. The first one finished was A* pathfinding, which I’ve known about for years but never understood until recently. It’s amazingly simple, which is always a bonus when implementing algorithms (so much less to screw up!).
I’m going to skip the nitty-gritty details, like why A* is an informed graph search algorithm (vs. an uninformed one like depth-first) or how it’s similar to Dykstra’s Shortest Path algorithm. Not because they’re not interesting topics (they are) but because it’s stuff you don’t really need to know to write your own A*. To optimize it, sure. Anyways… on to making it work.
You really only need to know three pieces of information at each step to do an A* search. I’m going to call the starting point S, the destination D, and the point currently under examination P.
- The first one is probably obvious, but you need to be able to tell if you’ve reached the destination or not. This could be trivial when there is only one D (i.e. if(P == D) ) like when you’re plotting the path a unit would move to, but could be more complicated when you have multiple destinations and any of them is fine, such as looking for the closest enemy unit to attack.
- Second, you need to know the actual cost to get from S to P. This is easily handled in the recursion.
- Lastly, you need an estimate of how far P is from D. It’s important that the estimate be less than or equal to the actual cost – underestimating is fine, but if you go over A* will no longer produce optimal paths.
The functions for the last two data points are commonly known as G and H, and the sum of the two values is the weight of a move in A* (F = G + H). That’s it… the whole formula. All you do to find the answer is explore the move with the lowest weight until you find the destination. As with any graph search you need an open and closed list (usually implemented as sorted lists or min-heaps). The code essentially looks like this:
open = 0 + h(start)
while(open not empty)
p = open.minvalue
closed.add(p)
if(p == dest)
return p
end if
open.add(p.successors)
end while
Granted, you’ll need some extra code to get all the successors to P (all of the moves possible from point P) and to construct the move path from P back to S. Using a class or struct for moves makes this easy because you can just keep track of the previous move and backtrack to the start (where the previous move would be empty). It also eliminates the need to keep a closed list (since you no longer need it to determine the path from S to D).
Anyways, that’s it! Simple, but pretty cool.
I’ve learned a lot of programming languages over the years. Some are good, some are good for certain applications, and others are well… crap. I’d say C– definitely falls somewhere between “specialized” and crap. It’s a subset of C used in BACI, a language used primarily to teach concurrency programming. That’s fine, except it leaves out all of the good parts of C that let you progress beyond “hello world”. Like pointers, structs, or floating point numbers.
I seriously never imagined myself having to write a queue using only arrays of integers (which of course means it can’t even be generic since the array must be of a fixed size), but having done so I find myself angry and bitter. I echo Frank Costanza’s sentiment when I say SERENITY NOW!
