Ok, I'll try and explain my query as best as possible. Basically, I have a map of a town that shows every road, path and alley, and I wish to store the layout of these various "paths" (ie. any traversable route between two consecutive junctions) into some data structure that I can perform various tasks on. The way I see it, I can either store data on each junction (with details of each road/path that comes out of it), or on each road/path (with details of the two junctions that are on either end). The idea is that I want to have a fairly simple data structure in a standard format that can be fed into a program so that program will be able to "understand" the layout of the town, knowing what roads connect to other roads, lengths of each road, etc, with one example aim being for the program to calculate efficient routes between various points in the town. In trying to figure out a simple way of doing this in the past, I came across the issue of what I should do in a situation where, for example, a long stretch of road has several roads branching off of it - would it be better to incorporate the possibility of "branches" into the data for each road, or should I split the stretch of road into sections that have junctions on either end for each branch that comes off of it? I don't really want to have to be as detailed as giving map coordinates as I don't think it's necessary for what I'm doing as it's just the general layout of the roads/paths I'm interested in and not the geographical or topographical layout. I hope I've been clear with what I'm asking, it's certainly not the easiest question in the world to put in words. Edit: I know that what I'm asking relates a lot to graph theory, a field which I have looked into and am interested in. Unfortunately, although I have found a lot of useful information on various algorithms I could perform, storing the map data in the first place seems to be the tricky task.

Ok, let's have a stab at this:

struct Junction {   int id;}struct Road {   Junction *leftJunction;   int leftJunctionType; //straight on, stop, give way, etc...   Junction *rightJunction;   int rightJunctionType;   int roadLength;}

The "straight on" junction type is if you have something like this:

       |=======*=======

The * is the junction, the | is a minor road, the = a major one.

The = either side of the * would have the type "straight on", since you don't have to do anything to continue on that road. The | would have a give way or stop type.

You are probably going to need some sort of linked-list on the Junction to keep track of all the Roads that connect to it.

Regards
elFarto

Both useful ideas, thank you. My problem is that it's proving difficult to work out how I can get the program to "understand" the overall topology of the town in order to navigate in a human-like manner. I'm looking into route-finding algorithms such as Dijkstra's and A*, but they would only really provide a short route without any real knowledge of the layout of the town as a whole. I guess you could say my goal would be for the program to know such things like the fact that Road A is only two junctions away from Road B, that the shortest route to landmark X from Road A contains a large number of different roads to navigate, that a particular area of town has a high density of one-way streets, etc. I guess you could say that this is more of an AI problem which I suppose it is, but before beginning to think of any "intelligence" behind the program, I first need to have all the necessary details of the town's areas and road layouts to be in a format that is easy for the program to understand, so that the program understands the layout of roads in the town as a whole and not just each road in isolation. Note that I do have all the information about the town that I will need.

I know that this is probably quite an ambitious task I've set myself, but I don't want to give up until I know for certain that it can't be done. Thank you again for your suggestions, elFarto and KulSeran, please keep them coming.

It really sounds like you've got all the details already, graphing, A* Roads requiring weighting values etc. So I'm not sure what you are asking for.

If it's how to automatically build the data then that is tricky, but possible, just have to look into image processing, although I suspect you'll want to at least draw an 'overlay' map to simplify the processing, i.e. using colour coding to mark junctions and roads etc.

However if its simply how to construct the layout in code, then my approach would be;

Define every junction as a node. A junction occurs any time two or more roads meet or a road ends. If landmarks are important then these can also become nodes. Each node contains data such as a display name (for convenience) its co-ordinates in the world and of course a list of other nodes it is directly connected to and included with that information is the cost of travelling down that part of the road.

You can model 'one way streets' by making the cost astronomical when going the wrong way from one node to the other, but in the opposite direction its cost is low. Of course its technically still possible for the AI to go the wrong way down this road, but a suitably large cost should prevent it. Otherwise simply add a boolean along with the cost to indicate if the road can be travelled in that direction or simply don't attach nodes if it means going the wrong way down a one way street.

The road costs can also be updated before searching for a path, to reflect say changes in how 'busy' a road might be at a specific time of day etc. Depending upon how much data you need for the roads, then perhaps the node object will contain a list of adjoining nodes and for each one a pointer to a road object. That way a road object can hold more information such as its name, cost to travel, modification rules to costs (e.g 7am-9am cost is doubled due to rush hour traffic) etc.

Once thats all done, its a simple case of implementing A*, although i've never got round to doing that for graph nodes, just plain grids, but I don't think there is any real complications.

Hope this helps

I have to agree with noisecrime. You have all the information you need, you just need to calculate suitable weights for each road, and all that boils down to is how much time it will take you to get from one end of the road to the other. So something like:

weight = average_speed_for_time_of_day / length_of_road

Give each junction a weight relative to its complexity, so a roundabout is more complicated than a simple T-junction. A straight-on type I mentioned above has a weight of 0.

The correct/best route should drop out of your algorithm.

Regards
elFarto

Excellent suggestions, thank you very much again. I have a couple of questions though.

Firstly, how do you think I should deal with traffic lights in terms of applying weighted values? Traffic lights are obviously present at junctions (and nowhere else in this town, I believe, though I'll have to confirm), but each set of traffic lights shines red for different periods of time depending on what road you are coming towards them from. For example:

A             B------X--------      |      |      |      | C

Let's say there are traffic lights at junction X. Now, I live in the UK so here we drive on the left. If you approach X along road B and want to turn down road C, you can only turn when no traffic from road A is turning down road C. But if you approach X along road A and want to turn down road C, you can only turn when all traffic along road B has stopped, and when traffic from C turning down B has stopped. This is of course made further complicated when the junction is a crossroads, and there are even further complications if, for example, road C is considered a minor road and thus the traffic coming out of C is stopped by traffic lights for longer periods of time than traffic coming out of A or B.

Any suggestions on what a way around this is? The only way I can think of right now is to hard-code several weights for each junction, one for each ordered pair of roads (one road being the entrance and the other being the exit), but then this requires a lot of hard-coding given that the graph for the overall town contains 340 junctions (though "junctions" includes dead-ends which frequently appear in a couple of housing estates).

My other question is somewhat easier to word. How would I deal with differing amounts of traffic at different times of day? I've decided on putting a simple function for each road with an input of timeOfDay, and an output of the weighted value (the function also takes into account the length and average speed). However, for the function to be able to use the time of day, there needs to be, again, hard-coded arbitrary values for different times of day for each road. I was thinking about doing values for every 15-minute interval between say 5AM and 10PM with a single value for the remaining 7-hour interval, how do you think that sounds? I chose 15 minutes because I think it's short enough that quick traffic-rushes can be taken into account like the rush of traffic when children are picked up from school (fairly significant where I live). Again though, this does seem to be making a lot of data. And there must surely be a more efficient and flexible way of storing different weights for different times of day, isn't there? The issue of differing amounts of traffic at different times of day also applies to junctions, and with traffic lights, as traffic lights are programmed to let through the most efficient number of vehicles down certain roads if those roads are particularly busy at certain times of day.

This project seems to be getting more complex and ambitious by the second, but I do feel that the more realistic the better. Thank you again for your patience!

I also live in the UK, and the term 'drive' greatly overestimates the quality of driving in this country :)

In response to your first question. On each Junction object you can add a field to represent if the junction has a set of traffic lights. You can also add 2 fields to the Road object, leftMaxWaitTime and rightMaxWaitTime. Simple put these fields contain in seconds the maximum red light time. You could modify this further to take into account time of day, e.g. *0.5 when not busy or *1.5 when busy.

As for coming up with these values, I can't think of anything that accurate (unless you have access to the exact timings of them). If you know how many lane each road has and it's speed limit, you could figure out some crude maximum capacity. You could then assign the values as such if A-B has twice the capacity of C, it would get half the red light time.

I think you need to come up with some function that returns a floating-point number representing global traffic level. You pass in the time of day and gives you some multiplier based on an average level of traffic. E.g. passing in midnight would give you a low number like 0.1, but passing in 8:30am would give you 2 or maybe 3, midday would be about 1. The graph should be quite low between 8pm and 7am, a steady arc between 7am and 8pm, with 2 peaks at morning and evening rush hour.

This could then be used to weight the traffic lights.

Regards
elFarto

Quote:Original post by DJNedFirstly, how do you think I should deal with traffic lights in terms of applying weighted values?

By just that, giving a junction node its own cost, based on whether the junction has traffic lights or not. You can make Zebra crossings and Pelican Crossing junction nodes with a cost too if you want.

I wouldn't bother doing anything more than that since you are rapidly increasing the complexity for minimal gain. So don't worry about time spent at red lights or waiting to turn right.

To avoid hard-coding values for each junction, just build an array of values for a fixed number of junction types, then assign each junction node a type (ID into the array) based on whether it has traffic lights, how many roads intersect etc to get its value. As the values are in a lookuptable, you can easily tweak them.

Quote:My other question is somewhat easier to word. How would I deal with differing amounts of traffic at different times of day?

Depends how complex you want to make it. For simplicity just create a 'traffic' array, where each entry represents 15 minutes of time (starting at say midnight) and the value represents a modifier to the cost of travelling down a road or link. So an array of 24*4 values.

Then when calculating the cost to traverse from one node to another multiply the normal road cost (usually based on its length and therefore time to travel) by the value in the array as indexed by the current time/15 mins.

So any entry in the traffic array that is within a 'rush' period has a value of say 2.0, whilst non-rush times have a value of 1.0 and at quiet times a value of say 0.5 (somewhat extreme values I don't suggest using them).

Of course not all roads should be affected the same by the 'traffic' values as some will not get as busy. You can factor this in by adding a modifier value 'popularity' to each road/link object so your cost calculation from a road/link object might look like (pseudo code)

cost = initialCost * trafficArray[timeOfDay] * popularity

where
initialCost = length of road/link between nodes
timeOfDay = currentTime converted to an index into traffic array
trafficArray = modifier value to represent traffic changes during rush hour
popularity = modifier value from 0.0 - 1.0 based on how popular road is.

This calculation would be called every time A* traversed down this road, to reflect changes in time of day as you drive to your destination. You would have to update the current time of day, by the time it would take to drive down this road, but only for this path, so each path would need its own timeOfDay property

Quote:This project seems to be getting more complex and ambitious by the second, but I do feel that the more realistic the better.

It is, but you need to clarify your aims and objectives. Although the outlines i've given can be coerced into working with the various changes and additional influences, it would be far better to understand the whole aim of the project first, both for yourself and those replying.

The level of complexity and involvement is dependant upon the purpose of the project. But there are really only two ways of going about it, either faked, where it gives a good impression, but is simple to code, or realistic, which might be accurate but vastly more complex to build. Mind you in both cases A* and some of the details I and the other posters have mentioned are still applicable.

Personally I'd first get a simple working version going, one that accurately determines routes by nothing more than the total distance travelled. From there you can change from distance to time and start accounting for increases in time due to junctions or rush-hour. After that you'll be in a far better position to determine just how realistic you want to make it and what properties/methods you'll need.

I couldn't go without replying to say thank you yet again. I'm currently working on uploading the data on the town into a usable format and will then try and get a simple A* implementation going before I think about how it can be made more realistic. If anyone has any more suggestions or thoughts, I'd be very interested to hear them.