Skip navigation

Portfolio of work done.

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.

Front side

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.

Link

Controls:

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

Info:

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.

New Version.

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.

Latest Version.

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.

 

Controls

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

Was thinking about how to implement level of detail in the pathfinding grid, as well as what method(s) I could use to speed up the path generation.

Dijkstra

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.

Linear

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.

BiDirectional

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.

A Star

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.

Interesting read – http://software.intel.com/en-us/articles/the-secrets-of-parallel-pathfinding-on-modern-computer-hardware/

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.

Link

Controls

————————

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.

Notes:

The bot will sometimes walk over solid nodes if a node in the path has been enclosed with solid nodes.

Uses Dijkstra’s algorithm.

Follow

Get every new post delivered to your Inbox.