Jedimark

• Posts: 2056
« on: 2004-02-10 11:29:02 »
I've currently got a real pain of an assignment to do at the moment basically simulating an "Autonomous Vehicle Control System" and one of the aspects of the system requires me to represent an entire road network somehow so it can be used to a) calculate shortest distance paths for a journey and b) navigate a vehicle on them.

Now I'm a bit stumped on the road network representation. Anyone got any good suggestions on a data structure for modelling a road network? I don't know much about Graph Theory but I'm researching that. Could it be done using a database? Obviously the roads need to have knowledge about junctions with other roads and speed limits etc.. so using databases looks tricky.

Cyberman

• Posts: 1572
« Reply #1 on: 2004-02-10 16:55:27 »
You need more than just distances between points on the road for example.

Think of a road like you would think of a 3d model instead.  The Road since it's not moving has a fixed BONE structure for that model.   The bones you can use for point distance calculations.

Remember it's a simulation which means you need to account for a physical model, hence think 3d instead of a series of data structures.  (the later comes from the physical information).

I suggest looking for online maps or creating a simple test course for your map.
3d models have a number of possible layers in them.
You have the physical description which is surfaces and textures adhered to those surfaces
Bone structure, if you push this here whole sets of points deform and stretch.
In your case you need a 3d planar surface called a walk map.  This walk map in your case is your road (in other words the car can only walk on that area.

Of course if the teacher wants something that's unrealistically simple heh.. a series of connecting points on a planar surface works just fine, use a cubic spline to determine when and where to turn (can't use beizer curves as they don't actually go through the point in this case you have to remain on the road ).

At this point you can create your data structure.  I suggest a maze solving alogrythm.  This is the same thing that is used by circuit board routers.  You being by finding the nearest node and going to it, you keep going until you either can't go anymore or hit your goal. At this point you return the list of locations and construct your travel plan from that.  The road is your 'safe' path for travel is all.

If you find two paths the shortest path should be choosen, safest path is another thing all together LOL.

Structure...

Lets assume your road way is a 2d planar surface (IE it's flatland).
You only need X and Y points of your road surface.   I'm not sure what you wish to do for how detailed it is but lets be simplistic.  You have a road surface and points in the center of it.

Points are connected (they are essentially a polyline).

Code: [Select]
`class intersection{ road_location *Connection; interesection *Next;};class road_location{ double Lattitude, Longitude; // or Y and X :) intersection *Branch;};`
you might want a few operators.. such as the difference returning a double ( IE A - B = the distance between the two points).

Also notice Branchs, they refer to other locations that this connects too.  If you wish to simplify this just use a fixed array instead of a list of intersections that this location connects too.

So your graph is basically a series of lists of interesections and the road locations they go to.
You traverse the graph between those locations to find if you can get there and the shortest path

How you traverse that path, well you have your books and you can have fun figuring out how to I guess

Cyb

• Posts: 53
« Reply #2 on: 2004-02-10 17:41:34 »
I did a similar project a few years ago as part of a CS course on data structures. I assume your instructor wants you to learn about how graphs can be represented as data structures since you are studying path length and things.

In my project I just used a 2 dimensional integer array which stored the distances between various cities. Using this array and things like Warshall's algorithm you can find the shortest path. You could also use Floyd's algorith if you need the actual path travelled.

Ofcourse your project is a little different (and more difficult) from mine since you have knowledge of speed limits and intersections so you probably couldn't use a integer to represent all that information but you could still use a 2d array of a class or structure that would contain more information.

mirex

• Posts: 1645
« Reply #3 on: 2004-02-10 17:51:26 »
if you need graphic interpretation, i would keep an array of road intersections (2d or 3d, depends on your needs) and array of roads, which will keep info about road length, speed limit, intersections indexes and more.

There are few algorithms for shortest-path-finding, they usually work with 2D array which size is number of road intersections ... it can be filled from above arrays.

ficedula

• Posts: 2174
« Reply #4 on: 2004-02-10 18:02:43 »
For roads, a 2d array probably wouldn't be a great representation. Let's say you have an 'intersection' not only where two or more roads join, but also (for consistencies sake) where the speed limit changes.

If you had 1000 road segments, since most intersections would only involve 3-4 segments, you have a few thousand intersections. A 2d array would have 1000x1000 = 1 million entries. Not efficient.

What would be better would be to store a list of intersections. Then for each intersection, store a list of intersections it's linked to, and how long it takes to get to each one.

Code: [Select]
`A----------B|         /|      D|   /| /C`

For something Really Simple like that, your data structure might look like:

A:     (B 20) (C 30)
B:     (A 20) (D 10)
C:     (A 30) (D 15)
D:     (B 10) (C 15)

So A is 20 minutes from B, and 30 minutes from B ... etc.

It's basically like a tree; each node has pointers to other nodes. (Technically, it's a graph).

If you don't care about time, only distance, store distance instead! If you care about both ... things become tricker later on, although from a data structure point of view you can store both values easily enough.

To generate the graph is easy enough, just use a "flood fill" type algorithm; start at one node, mark all of its neighbours, process all the neighbours, all *their* neighbours, etc...

To then find the best path - if you only care about ONE of time/distance, that's OK: use A* Search. A* is guaranteed to find the 'best' path (shortest/quickest, depending on which you're working off), and it's likely to do it quickly.

I don't believe there's any algorithm that's guaranteed to work quickly AND find the best; probably NP complete, i.e. you're screwed.

If you care about both distance and time ... the search will be harder  But I suspect you don't. Most path finding algorithms only care about time (for constant speed, that's the same as distance of course), and you can fudge them to take other things into account a *bit*.

• Posts: 2056