Artificial Intelligence Depot
Visiting guest. Why not sign in?
News, knowledge and discussion for the AI enthusiast.
FEATURES COMMUNITY KNOWLEDGE SEARCH  
Natural Language Understanding
Delivers a synthesis of major modern techniques in natural language processing. The approach is unique in its coverage of semantic interpretation and discourse alongside the foundational material in syntax.
More information at Amazon US UK

Reply to Message

Not registered yet?

The AI Depot has a focused community of friendly users. Rather than let anyone abuse the site at the brink of promiscuity, we prefer to let only those with an active interest participate... this simply requires registering.

Why not sign up!

Joining the site's community is completely free. You can then post messages freely, and customise your personal profile at will. Specific privileges will also be granted to you, like being able to access printer-friendly articles without restrictions. So, why not register?

Username:
Password:
Subject:
Email me when someone replies.
Body:

Parent Message

A Method for Navigation

Hi

I've been working with pathfinding algorithms for some time now, and to be honest, most of what I found either don't work in full 3D or rely on waypoints (which I can't stand). The only one that seems to suit what i need is the quake 3 aas. Not the actual implementation, just some of the ideas - basically, the idea of using volumes instead of waypoints. After many minutes (heh) of thinking, this is what I've come up with. It's not perfect, probably fatally flawed and stupidly ineffeciant, but hey, that's why I'm posting it here for you lot to poke holes into :). Right then...

The world is split into a set of axis-aligned bounding boxes (aabbs), called volumes. These make up the simplified representation used by the navigation system.

Kept as a structure to make upgrading easier.

typedef struct nav_volume_s
{
bbox_t Box;
}
nav_volume_t;

Now, each volume is tested to see if it intersects with any other volume. If so, a link is created.

typedef struct nav_link_s
{
uint32 Volume1;
uint32 Volume2;

uint32 PlaneID;

int8 PlaneSide1;
}
nav_link_t;

Volume1 and Volume2 are the two volumes that are connected (kept as V1/V2 and not VolumeCurrent and VolumeNext to allow for one link to represent travel in either direction. PlaneID is the index to the plane that splits the two volumes. This is the first part i'm having a little trouble with. Depending on the position and the size of the two boxes, anything from 1 to 4/5 planes can be created. Here's an example:

<img src="http://remnant.gamedev.net/vol.gif">

Although those two solutions can be solved pretty easily, i'm sure there's more that cant, especially when using 3D boxes, not 2D as used in the image. Anyway, the Plane is used by the navigation code to direct the agent into the next volume. PlaneSide1 is the side of the plane that Volume1 is on. It can either be +1 or -1. Again, this is used to make going from one volume to another easier. To get the plane side for Volume2, just flip the sign of PlaneSide1.

That's all well and good, but what about navigating between the volumes? Well, that's where the paths come in.

typedef struct nav_path_s
{
uint32 VolumeStart;
uint32 VolumeEnd;

uint32 LinkStart;
uint32 LinkNum;

uint32 Cost;
}
nav_path_t;

Unlike the links, paths are a one-way affair. This is because travelling from Start to End could involved a big drop, which would make it impossible to go from End to Start again. So, VolumeStart is the starting volume of the path, while VolumeEnd is... yep, you guessed it, the end of the path.

LinkStart is the index to an array of integers which in turn point to the array of links. The paths quite often share the link index with other paths, i.e.

Volume1-->Volume12-->Volume50

That is the path that needs to be followed.

The link index might read:

LinkIndex0 = 1
LinkIndex1 = 2

Link1 is V1 to V12. Link2 is V12 to V50.

Path:

VolumeStart = Volume1
VolumeEnd = Volume50

LinkStart = 1
LinkNum = 2

Now, what if you wanted to navigate from Volume12 to Volume50? Simple

VolumeStart = Volume1
VolumeEnd = Volume50

LinkStart = 2
LinkNum = 1

Simple data reuse. The first path uses two links, while the second (which is essentially a part of a path) uses only one of the links. Okay, i might not have explained it very well but you get the idea.

The final value is cost. Cost is how expensive it is to get to the destination. This will at present be based on time needed to get to destination (seems like a good one).

When searching for a path, the path with the smallest cost will be selected.

That's pretty much as far as i got. I will deal with entities and whatnot later on in the development. For now though, this should suffice.

(/me puts on fire-proof clothing) Any suggestions welcome...

typedef struct nav_volume_s
{
bbox_t Box;
}
nav_volume_t;

typedef struct nav_link_s
{
uint32 Volume1;
uint32 Volume2;

uint32 PlaneID;

int8 PlaneSide1;
}
nav_link_t;

typedef struct nav_path_s
{
uint32 VolumeStart;
uint32 VolumeEnd;

uint32 LinkStart;
uint32 LinkNum;

uint32 Cost;
}
nav_path_t;

typedef struct nav_world_s
{
nav_volume_t *Volumes;
nav_link_t *Links;
nav_path_t *Paths;
plane_t *Planes;
uint32 *LinkIndex;

uint32 VolumeNum;
uint32 LinkNum;
uint32 PathNum;
uint32 PlaneNum;
uint32 LinkIndexNum;
}
nav_world_t;

1 posts.
Tuesday 11 February, 13:01
Reply
path finding, which path?

Hello Sami

In the beginning of your posting you say in the second paragraph:

> The world is split into a set of axis-aligned bounding boxes
> (aabbs), called volumes. These make up the simplified
> representation used by the navigation system.

You mean you interpret the world in this way so you can apply your tools. But of course the world isn't so. How good is that path finding then. You can't know it, I think. What do you think.

I will tell you my way. The environment is in your computer or somewhere else. You go there and what do you find - you recognize things, food, dangers and all kind of things. Recognizing is a kind of repetition, but with variations, noise and real change. It's identifying in maybe a chaos. The environment is also a neural net! Of course. Dynamic like nature.

You learn when you burn a bodypart, never again that. Think of storing the info and learning all the time and the environment is first simple. It grows when you visit it. You jump over a stone. The environment lives as well. It changes by you and also without you. I call this bottom-up thinking and it's certainly codable.

There are also rather complex mathematical solutions where you work with cameras and a database with the environment. With clever techniques a robot can navigate in a real environment. I've seen a demonstration. Yes it works. An expensive solution.

Ed van der meulen

82 posts.
Wednesday 12 February, 05:16
Reply

Back to the Artificial Intelligence Depot.