This is router.m in view mode; [Download] [Up]
/****************************************************************
* *
* I C A O M a p - *
* *
* A n A v i a t i o n U t i l i t y *
* *
* *
* Copyright (C) 1993, 1994 Martin Pauly *
* *
* N e x t V e r s i o n *
* *
* Copyright (C) 1994 Stefan Leuker & Oliver Meyer *
* *
* This file may be freely distributed only if it includes *
* the above copyright notice. *
* *
****************************************************************/
/* icao -- router module */
#import "router.h"
#import <appkit/appkit.h>
OBJECT *currentroute[] = {NULL, NULL, NULL, NULL, NULL};
/* define default range in NM */
#define DEF_RANGE 5
int waypointtypes[100]; /* list of waypoint type IDs */
int numberofwaypointtypes;
static OBJECT *route_to, *route_from;
double route_distance;
void
router_radionav() /* select radio navigation waypoints */
{
waypointtypes[0] = O_VOR;
waypointtypes[1] = O_VOR_DME;
waypointtypes[2] = O_VORTAC;
waypointtypes[3] = O_TACAN;
waypointtypes[4] = O_NDB;
numberofwaypointtypes = 5;
}
int
rangecompare(const void *a, const void *b)
{
return (int)distance((*(OBJECT **) a)->location, route_to->location) -
distance((*(OBJECT **) b)->location, route_to->location);
}
/* find objects in range of a current position; only returns objects that
bring you closer to your destination; find no more then maxobj objects */
void
objects_in_range(OBJECT * position, OBJECT ** in_range, int *numfound,
int maxobj)
{
double startrange; /* range of current position's object */
OBJECT **templist;
int i, j, match;
templist = (OBJECT **) malloc(sizeof(OBJECT *) * 1000);
*numfound = 0;
startrange = 0; /* flying away from a VOR etc.? then use that
* range, too */
if ((position->type >= O_VOR) && (position->type <= O_TACAN))
if (position->range != UNKNOWN)
startrange = position->range;
else
startrange = DEF_RANGE;
if (templist)
{
/* go through object list */
for (i = 0; i < db_objects; i++)
{
match = 0; /* check if this is an allowed object type */
for (j = 0; j < numberofwaypointtypes; j++)
if (waypointtypes[j] == objectlist[i]->type)
match = 1;
if (match)
{
if ((distance(objectlist[i]->location, route_to->location) <
(distance(position->location, route_to->location))) ||
((position == route_from) &&
((objectlist[i]->type >= O_VOR) && (objectlist[i]->type <= O_TACAN))))
if (objectlist[i] != position)
if ((distance(objectlist[i]->location, position->location)
- startrange)
<= ((objectlist[i]->range != UNKNOWN) ?
objectlist[i]->range : DEF_RANGE))
{
templist[*numfound] = objectlist[i];
(*numfound)++;
}
}
}
/* sort objects by range from destination */
qsort(templist, *numfound, sizeof(OBJECT *), rangecompare);
/* copy the maxobj nearest objects to in_range array */
for (i = 0; i < maxobj; i++)
in_range[i] = templist[i];
if (*numfound > maxobj)
*numfound = maxobj;
free(templist);
}
}
/* find optimal route from position to route_to */
ROUTE
opt_route(ROUTE currentroute)
{
OBJECT *currentpos = currentroute.waypoints[currentroute.nextpoint - 1];
OBJECT *possible_next_points[REC_WIDTH];
ROUTE possible_route[REC_WIDTH];
int numpoints, i, minindex;
double olddistance;
/* don't go too deep into recursion */
if (!(currentroute.nextpoint < REC_DEPTH))
return currentroute;
/*
* first check if current route is too long (twice the shortest distance)
* already
*/
if (currentroute.distance > 2 * route_distance)
return currentroute;
/* check if we have reached destination already */
if (currentpos == route_to)
return currentroute;
/* check if we can reach the destination from here */
if ((currentpos->type >= O_VOR) && (currentpos->type <= O_TACAN))
if (distance(currentpos->location, route_to->location) <=
(currentpos->range != UNKNOWN ? currentpos->range : DEF_RANGE))
{
currentroute.waypoints[currentroute.nextpoint] = route_to;
currentroute.nextpoint++;
currentroute.distance += distance(currentpos->location, route_to->location);
return currentroute;
}
/* OK, now let's see where we can get from here... */
objects_in_range(currentpos, possible_next_points, &numpoints, REC_WIDTH);
/* if we didn't find any points, we can't use this route */
if (numpoints == 0)
return currentroute;
/* otherwise, test how we get on with several points... */
for (i = 0; i < numpoints; i++)
{
olddistance = currentroute.distance;
currentroute.waypoints[currentroute.nextpoint] = possible_next_points[i];
currentroute.nextpoint++;
currentroute.distance += distance(currentpos->location, possible_next_points[i]->location);
possible_route[i] = opt_route(currentroute);
currentroute.distance = olddistance;
currentroute.nextpoint--;
}
/* now check which of these routes is shortest */
minindex = 0;
for (i = 1; i < numpoints; i++)
if (possible_route[i].distance < possible_route[minindex].distance)
if (possible_route[i].waypoints[possible_route[i].nextpoint - 1] == route_to)
minindex = i;
return possible_route[minindex];
}
/* perform actual routing */
void next_findroute(char *wholetext, OBJECT * from, OBJECT * via1,
OBJECT * via2, OBJECT * via3, OBJECT * to)
{
ROUTE bestroute;
int i, j;
double totaldistance;
OBJECT *waypoints[5];
int usedwaypoints;
OBJECT *routepoints[REC_DEPTH * 4];
int usedroutepoints;
int success;
char desc[100], desc2[100];
double inbound;
usedroutepoints = 0;
success = 1;
/*
* Das scheint mir nicht ganz richtig!
* Was wenn in via1 nichts, wohl aber in via2 was steht?
*/
if ((from && to) && ((from != to) || ((via1) && (from != via1))))
{
usedwaypoints = 0;
waypoints[usedwaypoints++] = from;
if (via1)
waypoints[usedwaypoints++] = via1;
if (via2)
waypoints[usedwaypoints++] = via2;
if (via3)
waypoints[usedwaypoints++] = via3;
waypoints[usedwaypoints++] = to;
for (j = 0; j < usedwaypoints - 1; j++)
{
route_from = waypoints[j];
route_to = waypoints[j + 1];
route_distance = distance(route_from->location, route_to->location);
bestroute.waypoints[0] = route_from;
bestroute.nextpoint = 1;
bestroute.distance = 0; /* we haven't moved yet */
bestroute = opt_route(bestroute);
if (bestroute.waypoints[bestroute.nextpoint - 1] != route_to)
{
/* try to find a route without NDBs */
i = 0;
while ((i < numberofwaypointtypes) && (waypointtypes[i] != O_NDB))
i++;
if (i < numberofwaypointtypes - 1)
waypointtypes[i] = waypointtypes[numberofwaypointtypes - 1];
numberofwaypointtypes--;
bestroute.waypoints[0] = route_from;
bestroute.nextpoint = 1;
bestroute.distance = 0; /* we haven't moved yet */
bestroute = opt_route(bestroute);
}
if (bestroute.waypoints[bestroute.nextpoint - 1] != route_to)
success = 0;
else
for (i = (j ? 1 : 0); i < bestroute.nextpoint; i++)
routepoints[usedroutepoints++] = bestroute.waypoints[i];
}
sprintf(wholetext, "From %s %s\n", objecttypestring(from->type)
, from->name);
if (via1)
sprintf(wholetext+strlen(wholetext), "via %s %s\n"
, objecttypestring(via1->type), via1->name);
if (via2)
sprintf(wholetext+strlen(wholetext), "via %s %s\n"
, objecttypestring(via2->type), via2->name);
if (via3)
sprintf(wholetext+strlen(wholetext), "via %s %s\n"
, objecttypestring(via3->type), via3->name);
sprintf(wholetext+strlen(wholetext), "To %s %s\n\n"
, objecttypestring(to->type), to->name);
if (from != to)
{
sprintf(wholetext+strlen(wholetext)
, "direct course: Dist:%6.1f %2s, true track: %5.1f (direct)\n\n"
, distance(from->location, to->location) * UNIT_CHANGE(IPD_AUTOUNIT)
, UNIT_NAME(IPD_AUTOUNIT)
, truetrack(from->location, to->location));
}
if (!success)
strcat(wholetext, "Autorouter couldn't find a sufficient route!\n");
else
{
drawroutenumpoints = 0;
sprintf(wholetext+strlen(wholetext)
, "Inbound Waypoint Outbound %2s\n"
, UNIT_NAME(IPD_AUTOUNIT));
strcat(wholetext,
"--------------------------------------------------------------\n");
totaldistance = 0;
for (i = 0; i < usedroutepoints; i++)
{
drawroutepoints[drawroutenumpoints++] = routepoints[i]->location;
/* make description string */
if (routepoints[i]->type > 100)
{
if (routepoints[i]->type != O_WAYPOINT)
sprintf(desc, "%s %s", objecttypestring(routepoints[i]->type)
, routepoints[i]->name);
else
if (routepoints[i]->alias)
sprintf(desc, "%s %s", routepoints[i]->alias
, routepoints[i]->name);
else
sprintf(desc, "%s", routepoints[i]->name);
/* radio beacon */
if (routepoints[i]->type <= O_BASIC_RADIO_FACILITY)
if (routepoints[i]->frequency)
if (routepoints[i]->type == O_NDB)
{
if (routepoints[i]->frequency - (int)routepoints[i]->frequency)
sprintf(desc + strlen(desc), " (%5.1f)"
, routepoints[i]->frequency);
else
sprintf(desc + strlen(desc), " (%3.0f)"
, routepoints[i]->frequency);
} else
sprintf(desc + strlen(desc), " (%6.2f)"
, routepoints[i]->frequency);
} else
sprintf(desc, "%s", routepoints[i]->name);
/* make desc wide enough */
while (strlen(desc) < 39)
{
strcat(desc, " ");
if (strlen(desc) < 39)
{
strcpy(desc2, desc);
sprintf(desc, " %s", desc2);
}
}
desc[39] = 0; /* truncate in case it should have become too
* long */
if (i)
{
inbound = truetrack(routepoints[i]->location
, routepoints[i - 1]->location) + 180;
if (inbound > 360)
inbound -= 360;
totaldistance += distance(routepoints[i - 1]->location
, routepoints[i]->location);
if (i != usedroutepoints - 1)
sprintf(wholetext+strlen(wholetext)
, "%6.1f %s %5.1f %6.1f\n", inbound, desc
, truetrack(routepoints[i]->location
, routepoints[i + 1]->location)
, distance(routepoints[i]->location
, routepoints[i + 1]->location)*UNIT_CHANGE(IPD_AUTOUNIT));
else
sprintf(wholetext+strlen(wholetext), "%6.1f %s\n", inbound, desc);
} else
sprintf(wholetext+strlen(wholetext)
, " %s %5.1f %6.1f\n", desc
, truetrack(routepoints[i]->location
, routepoints[i + 1]->location)
, distance(routepoints[i]->location
, routepoints[i + 1]->location)*UNIT_CHANGE(IPD_AUTOUNIT));
}
strcat(wholetext,
"--------------------------------------------------------------\n");
sprintf(wholetext+strlen(wholetext)
, " total distance: %9.1f\n"
, totaldistance*UNIT_CHANGE(IPD_AUTOUNIT));
if (from != to)
sprintf(wholetext+strlen(wholetext)
, " detour compared to direct route: %9.1f\n"
, (totaldistance - distance(from->location, to->location))
* UNIT_CHANGE(IPD_AUTOUNIT));
}
}
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.