Clicking the sample image in the browser will launch that sample.
Something I forgot to mention. Programs on this blog will require the XNA Redistributable.
Joke business card I made for no reason.
Been spending most of my time lately coding this program.
Generates a maze according to user input and then allows the user to have a bot find paths through the generated maze.
Additionally, after the maze is created a second pass will be run to group areas of nodes up into clusters.
This can make finding paths easier, alternatively a low quality path using only clusters can be made very quickly.
Written in XNA and compiled on the Reach profile.
Escape – Quit
Tab – Toggle drawing of cluster map – the cluster map will be drawn above the node map
C – Clear path and teleport the bot to a random node
U – Find path from first node to last node using only clusters
F – Freeze the camera’s location on the bot
X – Toggle walls’ and floors’ opacity and turn off drawing nodes
R – Reset camera position
WASD – Move camera
Space – Move camera up
LCtrl – Move camera down
Left Click – Find path to selected node from the bot’s current node using clusters and nodes
LShift + Left Click – Find path to selected node from the bot’s current node using only nodes
PF Time: Time in milliseconds of how long it took for a path to be generated using only nodes
PF Ticks: Number of CPU cycles it took for a path to be generated using only nodes
PF Path Nodes: Number of nodes checked when computing path using only nodes
PFC Time: Time in milliseconds of how long it took for a path to be generated using clusters
PFC Ticks: Number of CPU cycles it took for a path to be generated using clusters
PFC Path Nodes: Number of nodes checked when computing path using clusters
PFC Path Clusters: Number of clusters checked when computing path using clusters
Tris: Number of triangles in memory
Tris Drawn: Number of triangles being drawn
FPS: Frames per second
ThreadCount: Number of active threads besides the main thread
Nodes: Number of nodes in the maze
Clusters: Number of clusters in the maze
Just a random program I wrote today.
The idea of the program was to test how many active bones I could manage to update before the framerate dropped below 60 fps.
Benchmark is about 12000 bones, set up so that each bone is parented by the previous one.
Each triangle is a bone, of which at the moment there are 128. I may decide to allow for the triangle/bone count to be dynamic in the future.
Here is the Link.
Rewrote the program. Bone count is at 40000 without too significant slowdown. The system runs smoothly if no lines are drawn.
Joints are still drawn, as they seem to have little effect on performance.
You can press space to toggle drawing of lines. All this really does is colour the system green.
Updated the program again. Managed to get textures skinned to the triangles and a simple navigation system in.
Moving the mouse moves the camera and scrolling the mouse wheel will zoom in and out.
Wrote a program that takes a list of tiles and tries to create the fewest number of boxes to fit the shapes made in the tiles.
I plan on using this to generate a 3D maze using multiple 2D levels generated using this code. Walls, ceilings and floors will be created based on the generated collision data.
Here is the Link.
Left Mouse – Toggle Tile Solid/Non-Solid
Escape – Quit
Space – Calculate Collision
Tab – Toggle Drawing Tiles
F – Create Checkerboard
C – Turn All Tiles Non-Solid
R – Reset Collison
Reworked the line drawing methods. The program can now draw 125000 lines without slowing down (possibly more).
You can check this by running the application and press Tab (this will set all nodes to traversable), then hit space to draw node links.
The number of lines that are being drawn will be displayed at the top of the screen.
You can find the program here: Link
This will find you the shortest path, but isn’t always used in games as it can be very slow finding a path to a destination location when there is a high node count.
Starts from the initial node, and visits the next cheapest, unvisited node to travel to. This continues until the node being visited is the destination.
Starts from the initial node and destination node and fills outwards from both nodes. This continues until one node has already been visited by the other node’s search. This can be faster or slower than Linear, based on the nodes’ locations. This is faster to complete if one node is enclosed and cannot be reached. It is slower however, if both nodes are enclosed in different areas with a similar enclosed area size.
Uses a heuristic, typically Manhattan to guess how far away the current node is from the destination. Manhattan is the X and Y (and possibly Z) difference the current node is from the destination node. A Star keeps moving towards the node that is closer to the destination, unless that node is already visited. This algorithm will not always return the shortest path, but is the cheapest to perform.
Parallel Path Finding
Not an actual algorithm, this is using separate threads on the CPU to find a path. Some games just dedicate a thread for path finding instead of spreading out the computations over multiple threads.
More to be added later.
A simple program that finds a path from the bot’s current position to the given destination.
The path will update if you change a node to be solid, but only when the bot is about to move to it.
Space – Toggle node link display – Draws the links between traversable nodes.
Tab – Convert all the nodes in the map to traversable.
Left Mouse Button – Have the bot find a path from it’s current node to the node the mouse is over.
Right Mouse Button – Toggle the solid state of the node the mouse is over. Won’t change if the bot is currently on the selected node.
The bot will sometimes walk over solid nodes if a node in the path has been enclosed with solid nodes.
Uses Dijkstra’s algorithm.