Tag Archive for XNA

Path Finding in XNA – Improving Basic Search

9 September 2011 Path Finding in XNA One comment

As we noted in the previous tutorial post our Graph class is very good at returning all possible paths, but cannot tell if one path is better than another.

Diagram showing connections between 4 nodes

Simple AI Path

In the case of the graph shown the possible routes from S to G would be either SAG or SABG. If we assume that the path finding is for an enemy tank and that the tank travels at a constant speed then SAG is faster than SABG.

However this may not always be the case. Say that the edge between nodes A and G intersects a swamp which slows the speed of by 70%. This would mean that route SABG is faster.

Diagram showing connections between 4 nodes including cost of each edge

Simple AI Path with Edge Cost

Luckily implementing a system to a system to take this in to account is not too difficult.

Note the diagram shows a number next to each edge. This is the edge cost which summarises how complex a given edge would be as part of any given path. How you define these values is up to you, it could be affected by the land conditions, incline, etc… but they should ultimately represent the amount of time it takes to travel along that given edge.

Knowing this we can say that the possible paths now have a cost. Path SAG has a cost of 11 where path SABG has a cost of 8. This would mean that path SABG is the more efficient route as the cost of path SAG is greater.

Read more

Path Finding in XNA – Basic Search / BFS

8 September 2011 Path Finding in XNA No comments

Creative use of search methods can solve many problems in game development, but often this solution is not appropriate. When developing a path finding AI you need to ensure you find a balance between the most efficient way of finding a solution, the most efficient solution and the chance of finding a solution.

Basic Search is the simplest form of path finding. It uses a series of points called nodes, which joined together create paths through your levels. The join between two nodes we will call an edge. Think of the nodes being motorway junctions, the road between junctions being an edge and the overall combination of one or more nodes and edges being a path.

Image showing connection of junctions to motorways

Motorway with Path's and Node's (ref: Google Maps)

The image above shows a typical stretch of motorway in the UK. The black line represents the path along the road cars take, they can join and leave at junctions, shown as red circles, which we would consider to be nodes.

Read more

Path Finding in XNA – Introduction

7 September 2011 Path Finding in XNA No comments

Path finding in games is a complicated issue and requires careful planning to ensure that your players do not get a negative experience from the game experience. In this many games have succeeded but also many have failed and whilst it might not be enough to cause your players to leave fully it is certainly a significant annoyance.

This tutorial series will show a number of path finding techniques and provide code examples for use in a simple 2D XNA game. Note however these techniques can be applied to many different programming languages and with a few modifications can be modified to use on a 3D game.

Each post will build on the content covered in the last post, so it is strongly recommended you read the posts in order as this will give you a fuller understanding of the subject matter.

At the end of each post a full code example will be available, where possible I will supply the assets I have used in the creation of this tutorial.

Please note I do not claim to be an expert in C# or XNA and there may well be better ways to do this, if so please post below and hopefully I can make modifications to the tutorials to provide a better learning resource for everyone.

Building a Terrain Engine in XNA – Part 0

30 May 2011 Building a Terrain Engine in XNA No comments

When browsing through 3D code examples online I have found a number of very nice looking 3D terrain engines for XNA, however there is very little in the way of tutorials or information on how these people have achieved certain effects. To continue my investigation I found a very insightful tutorial series by Shamus Young on one of his blogs Twenty Sided.

In his Terrain Tutorial he talks about a number of techniques he used to complete a terrain engine. Whilst his code was written in C++ and OpenGL I am attempting to transfer a number of his ideas to work in XNA and because of this most of my aims will align to his.

Read more