OK... no secret here that our debut title, "Airline Traffic Manager" involves passengers booking on flights. I know that for passengers creating their ittinerary, A* is the obvious way to go. However, there are some quirks to this. I am trying to decide how to create the map file. On the first conceptual level, a city will have service to n other cites - up to the maxiumum # of cities in the game (in theory, a hub city COULD have direct flights to all the others). 2nd level of thought... there could be (and will be) multiple flights from a to b. Each of these flights will have it''s own characteristics that equate to the path cost. In addition, only flights that depart from b after and within 2 hours of the first flight''s arrival are valid for that path. So, the issue is that, rather than an array of 8 pointers to adjacent squares on a chart, we have to account for x number of possible node connections where: x = [#cities] * [Max#Flights to each city per day] I know that at each node, I can include a quick check of all the other paths that connect from there to determine if the departure time is valid (> arrtime && < arrtime + 2hours). The problem is, I am loathe to a) reserve a huge amount of space in my array or b) limit the amount of possible destinations and/or flights out of a city. Ideas? Dave Mark - President and Lead Designer Intrinsic Algorithm - "Reducing the world to mathematical equations!" RIPPL Sports - NFL Statistical Analysis and Prediction System

Hi Dave,

Are you asking what the best way of representing the flight path data is?

If so, then my suggestion would be to create a digraph. Your pathfinding algorithm can use indexes into the graph to do its stuff.

Also, if your passenger''s itineraries have to be designed so that they pass through each of their chosen cities only once according to some criteria, then you have a version of the ol'' Travelling Salesman Problem on your hands. So A* may not be your best option…




ai-junkie.com

Each pax has an origin and a destination. Each pax will have to look at the available flights and, based on a number of criteria that compare their preferences to the info on the flights, select an itinerary to get from that origin to the destination.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System

Your post suggests that the connectivity of the graph/tree varies depending on the previous choices made by the agent... so that, the links available at city B to other cities will depend on the time that a flight from city A to B gets in. Is this correct?

If this is correct, then I suspect that you will need to add time as a dimension in your tree. Thus, two flights arriving at a city that are more than two hours apart can actually be considered as two paths in the graph that terminate at different nodes in the tree. This should negate the problems of identifying different path costs for the same path (because now they''re not the same path).

As to storage of this information... you have a tree with a variable branching factor... you shouldn''t use arrays for this sort of tree. Rather, use a linked list at each node to represent connectivity to successor nodes.

Cheers,

Timkin

The problem with a simple linked list or tree is that there can be litterally an infinate number of connections from any given node. Let''s throw together an example:

A = Origin
Z = Destination

The flight databasae holds the following:
(Flt#, Origin, Dest, Dep, Arr)

100: A-Z 9-11
200: A-B 8-9
201: A-B 9-10
300: A-C 8-9
301: A-C 9-10
400: B-Z 10-11
401: B-Z 11-12
500: C-Z 10-11
501: C-Z 11-12

Obviously, our pax could take flight 100 (direct). He could also take the following itineraries:
200, 400 = A-B-Z
200, 401 = A-B-Z
201, 400 = A-B-Z
201, 401 = A-B-Z
300, 500 = A-C-Z
300, 501 = A-C-Z
301, 500 = A-C-Z
301, 501 = A-C-Z

Now, conventional map systems would have each city as a different node. If this were the case, node A would be linked to B, C and Z. However, we now have to represent the idea that A-B can be done by either flight 200 or flight 201. As you say, Timkin, this would involve some sort of time dimension... or a "Z" value. The interesting point here is that this new "Z" location is more important than the X, Y location of a city.

The actual final fitness of each leg (and therfore the total itinerary) is based on comparing various properties of the flight with preferences of the passenger. That is, there is no ONE fitness value that can be pre-calculated. I will be having to apply the various properties of the flight combined with the preferences of the pax to determine the fitness level of each leg as we go. One of those preferences applies to the length of the trip - but this is only ONE of the factors and may be the least important for the passenger in question. That makes determining a relevant hueristic kinda nebulous. *shrug*

What I would expect to have to do is recalculate the map every time a flight is either added or deleted to get some sort of network on possibilities. Then once all the possible initial flights are selected (which have a wider time window than the connecting flights), I can itterate through those flights and their pre-calculated available connections. I would have to calculate the fitness values of all the next series of connecting flights before I sorted them, I realize.

I guess the trick to all of this just that there isn''t a fixed number of connections to select from like there are in nice tidy maps.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System

The problem with a simple linked list or tree is that there can be litterally an infinate number of connections from any given node

Maybe I misunderstand, but you only add a city connection to a graph node if the plane can fly directly to it. In your example (because we stay on Earth), even given the scheduling considerations, there will always be a finite amount of connections.








ai-junkie.com

But there can be many direct flights from A to B during the course of a day. Remember, there are also going to be multiple airlines here as well. Between some busy city pairs, there could be 5 or more different flights from A to B inside an hour. Throw multiple hours into the mix and you see how complicated this gets quickly.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System

Oh, I appreciate it''s a complicated problem Dave. But the graph creation is reasonably simple. Even with all those flights. If you do it using hash tables then inserting and deleting edges (the flights) or nodes(the cities) will be fast and efficient.

It''s how the graph is searched that is problematical.

by the way, what''s a "pax"?



ai-junkie.com

(pax = shorthand for passengers... sorry)

Can you help me out with the hash table concept... I remember looking it up on a conceptual level before, but I didn''t get in too deep on it. How would we apply it here?

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System

This problems seems solvable with dynamic programming. How''s this:

Each city holds a linked list to all the flights that depart from the city. Each flight has a number of variables, which can be combined in different ways to produce a heuristic function for how good that ride is. Divide your pax in a few distinct categories, each category having a different heuristic (favoring speed or comfort or safety records or time wasted or business facilities etc.) Let''s say each flight has a negative heuristic value and the heuristic value for a travel is the sum of the value of each flight (and of each wait) in the travel. Each passanger wants to get the value as high as possible.

Now, for each city, for each pax category (for each heuristic), do this:

Calculate the best (according to the current heuristic) way to get there in 1, 2, 3, ... hours. Here''s where the dynamic thing enters stage.

Have a 2d array with the city as a dimension and time as another dimension. I assume all flights launch and land only at fixed hours. The meaning of a x/y cell in this table is: "The best way to get to city x in y hours is worth table[y][x] heuristic points"

Fill the array with a _very_ large negative number. Set to 0 the value of current city/time 0 in the table (the passanger is already at the airport). Now you run through all the cells in the table, starting with the present and advancing one hour at a time. At each cell, you consider boarding any flight that departs from that city at that hour or waiting another hour.

The result of each decision is easily calculated: you get a destination city (the same if your passanger waits), a destination hour (current cell time + 1 for waiting, current time + flight time else) and a heuristic specific cost (current cell cost + flight cost/waiting cost). You basically get a new potential value to store in your table. Compare this value against the one already in the table. Update the table only if the new cost is better.

Finding the best paths for each passanger is pretty easy from now on.

Run this algorithm at each hour for each city for each heuristic. Complexity is:
no of cities squared * hours ahead * no of flights departing in a city * number of heuristics. For 200 cities, 24 hours ahead, 10 heuristics and 10 flights for each city, you get something like 100.000.000 of operations.

Actually, this sounds a lot like what Timkin proposed.