rondje/ 0000755 0063040 0023565 00000000000 11511100422 011364 5 ustar visser staf rondje/RoadFinder/ 0000755 0063040 0023565 00000000000 11250240347 013414 5 ustar visser staf rondje/RoadFinder/graph/ 0000750 0063040 0023565 00000000000 11250240414 014503 5 ustar visser staf rondje/RoadFinder/graph/queue/ 0000750 0063040 0023565 00000000000 11236250147 015637 5 ustar visser staf rondje/world.nut 0000640 0063040 0023565 00000074345 11253416233 013271 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* Copyright 2008-2009 Marnix Bakker, Willem de Neve, Michiel Konstapel and Otto Visser.
* Suggestions/comments and bugs can go to: rondjeomdekerk@konstapel.nl
*/
require("RoadFinder/graph/queue/BinHeap.nut");
require("util.nut");
require("route.nut");
require("builder.nut");
// NOTE: these values are designed to create areas which don't overlap
// which is important so that we don't confuse pickup and dropoff stations
const DISTRICT_DISTANCE = 5;
const DISTRICT_RADIUS = 2;
const DROPOFF_DISTANCE = 8; // further out reduces congestion, but closer in means we can build it for smaller towns
const DROPOFF_RADIUS = 2;
enum Dropoffs {
NORTH_WEST
NORTH_EAST
SOUTH_WEST
SOUTH_EAST
};
class World {
numConnections = 0;
producers = null;
consumers = null;
towns = null;
routeList = null;
networks = null;
constructor() {
numConnections = 0;
producers = [];
consumers = [];
networks = [];
routeList = [];
}
/**
* Construct a model of the world: producers, consumers and routes.
*/
function Map() {
// keep old data available until we're done mapping
local newRouteList = [];
local newNetworks = [];
local tick = GetTick();
producers = Industry.FindServicedProducers();
consumers = Industry.FindServicedConsumers();
towns = Town.FindServicedTowns();
Debug("Finding serviced destinations took " + (GetTick() - tick) + " ticks");
// follow the road networks from all stations
tick = GetTick();
foreach (producer in producers) Trace(newNetworks, producer);
ManageVehicles();
foreach (consumer in consumers) Trace(newNetworks, consumer);
ManageVehicles();
foreach (town in towns) Trace(newNetworks, town);
ManageVehicles();
Debug("Tracing road networks took " + (GetTick() - tick) + " ticks");
tick = INSTANCE.GetTick();
local connections = {};
foreach (network in newNetworks) {
foreach (destination1 in network.destinations) {
foreach (destination2 in network.destinations) {
local distance = AIMap.DistanceManhattan(destination1.GetLocation(),destination2.GetLocation());
if (distance > MIN_DISTANCE && distance < MAX_DISTANCE) {
connections[Key(destination1, destination2)] <- network;
}
}
}
}
Debug("Creating connection graph took " + (GetTick() - tick) + " ticks");
if (connections.len() == numConnections) {
// no change, no need to continue
return;
}
numConnections = connections.len();
Debug("New connections!");
foreach (producer in producers) {
// Debug("Serviced producer: " + producer.GetName() + producer.GetProduction() + " units of " + producer.GetCargoLabel());
foreach (consumer in consumers) {
local cargoID = producer.GetCargo();
if (consumer.AcceptsCargo(cargoID)) {
// Debug("Serviced consumer: " + consumer.GetName() + " accepts " + producer.GetCargoLabel());
local key = Key(producer, consumer);
if (key in connections) {
local network = connections[key];
local route = Route(producer, consumer, network);
if (route.IsBuildable()) {
//newRouteHeap.Insert(route, -route.GetRouteValue());
newRouteList.append(route);
}
}
}
}
ManageVehicles();
}
tick = GetTick();
// consider two connected towns two routes, A->B and B->A
foreach (town in towns) {
foreach (town2 in towns) {
if (town != town2) {
local key = Key(town, town2);
if (key in connections) {
local network = connections[key];
// add routes for each city district
foreach (district in town.GetDistricts()) {
local dropoff = FindClosestDropoff(district, town2);
local route = Route(district, dropoff, network);
if (route.IsBuildable()) {
//newRouteHeap.Insert(route, -route.GetRouteValue());
newRouteList.append(route);
}
}
}
}
}
ManageVehicles();
}
Debug("Finding connected towns took " + (GetTick() - tick) + " ticks");
routeList = newRouteList;
networks = newNetworks;
}
function Key(destination1, destination2) {
return destination1.GetName() + "-" + destination2.GetName();
}
/**
* Returns an unordered list of routes.
*/
function GetRouteList() {
return routeList;
}
function SetRouteList(routeL) {
routeList = routeL;
}
function GetNetworks() {
return networks;
}
/**
* Follow the roads from all stations at a destination
* and determine which stations are connected.
*/
function Trace(networks, destination) {
local stations = destination.GetStations();
foreach (station in stations) {
if (GetNetwork(networks, station) == null) {
local newNetwork = FindConnectedStations(station);
networks.append(newNetwork);
}
}
}
/**
* Return a network in the list of networks that contains the given station,
* or null if there isn't one.
*/
function GetNetwork(networks, station) {
foreach (network in networks) {
if (network.Contains(station.stationID)) return network;
}
return null;
}
/**
* Find the dropoff in the town that is closest to the given district.
*/
function FindClosestDropoff(destination, town) {
local closest = null;
local distance = 1000000;
foreach (dropoff in town.dropoffs) {
local newDistance = AIMap.DistanceManhattan(destination.GetLocation(), dropoff.GetLocation());
if (newDistance < distance) {
closest = dropoff;
distance = newDistance;
}
}
return closest;
}
/**
* See if a route exists between two cargo-matched industries.
* @return the (first) network in which they are connected
*/
function FindConnectingNetwork(networks, producer, consumer) {
//Debug("Looking for route between " + producer.GetName() + " and " + consumer.GetName());
local sourceStations = producer.GetStations();
local sinkStations = consumer.GetStations();
foreach (sourceStation in sourceStations) {
// Debug("Source " + sourceStation.stationID + " @ " + producer.GetName());
local network = GetNetwork(networks, sourceStation);
if (!network) continue;
foreach (sinkStation in sinkStations) {
if (network.Contains(sinkStation.stationID)) {
// Sign(sinkStation.GetLocation(), sinkStation.stationID + " accepts " + producer.GetCargoLabel());
// Debug(sinkStation.stationID + " at " + consumer.GetName() + " connects to " + sourceStation.stationID + " at " + producer.GetName());
return network;
}
}
}
return null;
}
/**
* Return a Network starting at the given station.
*/
function FindConnectedStations(station) {
local stationTile = station.GetLocation();
local network = Network();
network.stations.append(station.stationID);
Follow(stationTile, network.tiles, network.stations);
foreach (stationID in network.stations) {
// if a station is built between looking for serviced destinations and coming here,
// there won't be a Station object for it
local station = Station.GetStation(stationID);
if (station) network.destinations.append(station.GetDestination());
}
return network;
}
function Follow(tile, visitedTiles, stationIDs) {
// manage vehicles every N tiles
if (visitedTiles.Count() % 100 == 0) {
ManageVehicles();
}
local roads = ConnectedRoads(tile, visitedTiles, stationIDs);
if (roads.Count() == 0) return;
for (local road = roads.Begin(); roads.HasNext(); road = roads.Next()) {
visitedTiles.AddTile(road);
Follow(road, visitedTiles, stationIDs);
}
}
function ConnectedRoads(tile, visitedTiles, stationIDs) {
local connected = AITileList();
local adjacent = AITileList();
adjacent.AddTile(tile - AIMap.GetTileIndex(1,0));
adjacent.AddTile(tile - AIMap.GetTileIndex(0,1));
adjacent.AddTile(tile - AIMap.GetTileIndex(-1,0));
adjacent.AddTile(tile - AIMap.GetTileIndex(0,-1));
for (local neighbourTile = adjacent.Begin(); adjacent.HasNext(); neighbourTile = adjacent.Next()) {
if (visitedTiles.HasItem(neighbourTile)) continue;
if (RoadsConnected(tile, neighbourTile)) {
connected.AddTile(neighbourTile);
} else if (TunnelOrBridgeConnected(tile, neighbourTile)) {
connected.AddTile(GetOtherEnd(neighbourTile));
}
if (StationConnected(tile, neighbourTile)) {
local stationID = AIStation.GetStationID(neighbourTile);
stationIDs.append(stationID);
if (!connected.HasItem(neighbourTile)) connected.AddTile(neighbourTile);
}
}
return connected;
}
function RoadsConnected(tile, neighbourTile) {
return AIRoad.IsRoadTile(neighbourTile) && AIRoad.AreRoadTilesConnected(tile, neighbourTile);
}
function TunnelOrBridgeConnected(tile, neighbourTile) {
return (AITunnel.IsTunnelTile(neighbourTile) || AIBridge.IsBridgeTile(neighbourTile)) &&
AIRoad.AreRoadTilesConnected(tile, neighbourTile);
}
function GetOtherEnd(tile) {
if (AITunnel.IsTunnelTile(tile)) return AITunnel.GetOtherTunnelEnd(tile);
if (AIBridge.IsBridgeTile(tile)) return AIBridge.GetOtherBridgeEnd(tile);
throw "not a bridge or tunnel";
}
/**
* See if a station is connected: the road tile is connected to the
* front or back station tile.
*/
function StationConnected(roadTile, stationTile) {
return AIRoad.IsRoadStationTile(stationTile) && (
AIRoad.GetRoadStationFrontTile(stationTile) == roadTile ||
AIRoad.IsDriveThroughRoadStationTile(stationTile) && AIRoad.GetDriveThroughBackTile(stationTile) == roadTile
);
}
}
/**
* A network is a set of connected road tiles and the stations and destinations they connected.
*/
class Network {
tiles = null;
stations = null;
destinations = null;
constructor() {
tiles = AITileList();
stations = [];
destinations = [];
}
function Contains(stationID) {
return IndexOf(stations, stationID) != -1;
}
}
class MapObject {
location = 0; // location TileIndex
constructor(location) {
this.location = location;
}
function GetLocation() {
return location;
}
}
class Sign extends MapObject {
id = 0;
constructor(location, text) {
MapObject.constructor(location);
id = AISign.BuildSign(location, text);
}
}
/**
* A source or destination for cargo (including passengers).
*/
class Destination extends MapObject {
cargoID = 0;
myStation = null;
stations = null;
constructor(location, cargoID) {
MapObject.constructor(location);
this.cargoID = cargoID;
this.myStation = null;
this.stations = [];
}
/**
* Destination name.
*/
function GetName();
/**
* Return an AITileList of tiles where cargo can be picked up.
*/
function GetPickupArea();
/**
* Return an AITileList of tiles where cargo can be dropped off.
*/
function GetDropoffArea();
/**
* Return an AITileList of the area in which we may find stations for this destination.
*/
function GetStationArea();
/**
* Station type: AIStation.STATION_BUS_STOP or AIStation.STATION_TRUCK_STOP.
*/
function GetStationType();
/**
* Returns whether this destination still exists, since industries can disappear (esp. oil wells).
*/
function Exists() {
// default to true; overridden in Industry
return true;
}
function GetCargo() {
return cargoID;
}
function GetCargoLabel() {
return AICargo.GetCargoLabel(cargoID);
}
function GetStations() {
FindStationsInternal();
// Debug(GetName() + " has " + stations.len() + " stations: " + ArrayToString(stations));
return stations;
}
function GetMyStation() {
// see if GetStations() already found it
if (!myStation) FindStationsInternal();
return myStation;
}
function SetMyStation(station) {
this.myStation = station;
}
function GetMyDepot() {
return Depot.GetDepot(this);
}
function FindStationsInternal() {
stations.clear();
myStation = null;
local area = GetStationArea();
area.Valuate(AIRoad.IsRoadStationTile);
area.KeepValue(1);
for (local tile = area.Begin(); area.HasNext(); tile = area.Next()) {
local stationID = AIStation.GetStationID(tile);
local station = Station(stationID, tile, this);
stations.append(station);
// if we find multiple stations of our own, use the closest
if (AICompany.IsMine(AITile.GetOwner(tile)) && AIStation.HasStationType(stationID, GetStationType())) {
if (myStation == null || IsCloser(station))
myStation = station;
}
}
}
/**
* See if this station is closer than myStation (must not be null).
*/
function IsCloser(station) {
local newDistance = AIMap.DistanceManhattan(station.GetLocation(), this.GetLocation());
local currentDistance = AIMap.DistanceManhattan(myStation.GetLocation(), this.GetLocation());
return newDistance < currentDistance;
}
}
class Town extends Destination {
townID = 0;
dropoffs = null;
districts = null;
constructor(townID, cargoID) {
if (!AITown.IsValidTown(townID)) throw "Invalid townID";
Destination.constructor(AITown.GetLocation(townID), cargoID);
this.townID = townID;
this.dropoffs = [];
this.districts = [];
}
function GetName() {
return RemoveTrailingNull(AITown.GetName(townID)) + " " + townID;
}
/**
* Calculate an estimated town radius based on population.
*/
function GetRadius() {
return Sqrt(GetPopulation()/100) + 3;
}
function GetStationArea() {
local area = AITileList();
SafeAddRectangle(area, AITown.GetLocation(townID), GetRadius());
return area;
}
function GetStationType() {
return AIStation.STATION_BUS_STOP;
}
function IsServiced() {
return GetStations().len() > 0;
}
function GetPopulation() {
return AITown.GetPopulation(townID);
}
function GetProduction() {
return AITown.GetMaxProduction(townID, GetCargo());
}
function GetDistricts() {
return districts;
}
/**
* Create a list of serviced towns.
*/
static function FindServicedTowns() {
local towns = [];
local list = AITownList();
for (local townID = list.Begin(); list.HasNext(); townID = list.Next()) {
local town = Town(townID, PASSENGERS);
if (town.IsServiced()) {
towns.append(town);
local center = District(town, PASSENGERS, Districts.CENTER);
foreach (sector in [Dropoffs.NORTH_WEST, Dropoffs.NORTH_EAST, Dropoffs.SOUTH_WEST, Dropoffs.SOUTH_EAST]) {
local dropoff = PassengerDropoff(town, sector);
if (dropoff.GetDropoffArea().Count() > 0) town.dropoffs.append(dropoff);
}
town.districts = [];
// (only) if there are no dedicated dropoffs available, drop people off at the city center
// in this case, the town is too small to generate passengers; just use it as a dropoff
if (town.dropoffs.len() == 0) {
town.dropoffs.append(center);
} else {
// we have at least one dedicated dropoff
town.districts.append(center);
local sectors = [];
if (town.GetPopulation() > 1000) {
sectors.append(Districts.NORTH);
}
if (town.GetPopulation() > 2000) {
sectors.append(Districts.SOUTH);
}
if (town.GetPopulation() > 3000) {
sectors.append(Districts.WEST);
}
if (town.GetPopulation() > 4000) {
sectors.append(Districts.EAST);
}
foreach (sector in sectors) {
local district = District(town, PASSENGERS, sector);
if (district.GetPickupArea().Count() > 0) town.districts.append(district);
}
}
}
}
return towns;
}
}
class District extends Destination {
town = null;
district = null;
constructor(town, cargoID, district) {
local direction;
switch (district) {
case Districts.CENTER: direction = [ 0, 0]; break;
case Districts.NORTH: direction = [-1, -1]; break;
case Districts.SOUTH: direction = [ 1, 1]; break;
case Districts.WEST: direction = [ 1, -1]; break;
case Districts.EAST: direction = [-1, 1]; break;
}
local location = town.GetLocation() + AIMap.GetTileIndex(direction[0] * DISTRICT_DISTANCE, direction[1] * DISTRICT_DISTANCE);
Destination.constructor(location, cargoID);
this.town = town;
this.district = district;
}
function GetDistrict() {
return district;
}
function GetName() {
local suffix;
switch (district) {
case Districts.CENTER: suffix = "Center"; break;
case Districts.NORTH: suffix = "North"; break;
case Districts.SOUTH: suffix = "South"; break;
case Districts.WEST: suffix = "West"; break;
case Districts.EAST: suffix = "East"; break;
}
return town.GetName() + " " + suffix;
}
function GetStationArea() {
local area = AITileList();
SafeAddRectangle(area, GetLocation(), DISTRICT_RADIUS);
return area;
}
function GetStationType() {
return AIStation.STATION_BUS_STOP;
}
function GetPopulation() {
return town.GetPopulation() / town.GetDistricts().len();
}
function GetProduction() {
return town.GetProduction() / town.GetDistricts().len();
}
function GetPickupArea() {
local area = AITileList();
local roads = AITileList();
SafeAddRectangle(roads, GetLocation(), DISTRICT_RADIUS);
roads.Valuate(AIRoad.IsRoadTile);
roads.KeepValue(1);
area.AddList(roads);
local clear = AITileList();
SafeAddRectangle(clear, GetLocation(), DISTRICT_RADIUS);
clear.AddList(GetStationArea());
clear.Valuate(AITile.IsBuildable);
clear.KeepValue(1);
area.AddList(clear);
// for suburbs, only consider tiles that capture passengers from several tiles
if (district != Districts.CENTER) {
area.Valuate(AITile.GetCargoProduction, PASSENGERS, 1, 1, BUS_STATION_RADIUS);
area.KeepAboveValue(12); // out of a 49 tile area
}
return area;
}
function GetDropoffArea() {
return GetPickupArea();
}
}
class PassengerDropoff extends Destination {
town = null;
sector = null;
constructor(town, sector) {
local direction;
switch (sector) {
case Dropoffs.NORTH_EAST: direction = [-1, 0]; break;
case Dropoffs.NORTH_WEST: direction = [ 0,-1]; break;
case Dropoffs.SOUTH_EAST: direction = [ 0, 1]; break;
case Dropoffs.SOUTH_WEST: direction = [ 1, 0]; break;
}
// NOTE: stay out of the areas where we might find pickup stations or we'd confuse the two types
local location = town.GetLocation() + AIMap.GetTileIndex(direction[0] * DROPOFF_DISTANCE, direction[1] * DROPOFF_DISTANCE);
Destination.constructor(location, PASSENGERS);
this.town = town;
this.sector = sector;
}
function GetName() {
local suffix;
switch (sector) {
case Dropoffs.NORTH_EAST: suffix = "NE"; break;
case Dropoffs.NORTH_WEST: suffix = "NW"; break;
case Dropoffs.SOUTH_EAST: suffix = "SE"; break;
case Dropoffs.SOUTH_WEST: suffix = "SW"; break;
}
return town.GetName() + " " + suffix + " Dropoff";
}
function GetStationArea() {
local area = AITileList();
SafeAddRectangle(area, GetLocation(), DROPOFF_RADIUS);
//for (local tile = area.Begin(); area.HasNext(); tile = area.Next()) Sign(tile, GetName());
return area;
}
function GetStationType() {
return AIStation.STATION_BUS_STOP;
}
function GetProduction() {
return 0;
}
function GetPickupArea() {
return AITileList();
}
function GetDropoffArea() {
local area = AITileList();
local roads = GetStationArea();
roads.Valuate(AIRoad.IsRoadTile);
roads.KeepValue(1);
area.AddList(roads);
local clear = AITileList();
clear.AddList(GetStationArea());
clear.Valuate(AITile.IsBuildable);
clear.KeepValue(1);
area.AddList(clear);
// keep tiles that accept enough passengers
// an acceptance of 8 is required to accept a cargo,
// and we don't want the first house torn down making our station useless
area.Valuate(AITile.GetCargoAcceptance, PASSENGERS, 1, 1, BUS_STATION_RADIUS);
area.KeepAboveValue(16);
return area;
}
}
class Industry extends Destination {
industryID = 0;
numStations = 0;
constructor(industryID, cargoID) {
if (!AIIndustry.IsValidIndustry(industryID)) throw "Invalid industryID";
Destination.constructor(AIIndustry.GetLocation(industryID), cargoID);
this.industryID = industryID;
this.numStations = 0;
}
function GetName() {
return RemoveTrailingNull(AIIndustry.GetName(industryID)) + " " + industryID;
}
function GetStationArea() {
local area = AITileList();
area.AddList(AITileList_IndustryAccepting(industryID, TRUCK_STATION_RADIUS));
area.AddList(AITileList_IndustryProducing(industryID, TRUCK_STATION_RADIUS));
return area;
}
function GetStationType() {
return AIStation.STATION_TRUCK_STOP;
}
function Exists() {
return AIIndustry.IsValidIndustry(industryID);
}
/**
* Return whether this industry has stations.
*/
function IsServiced() {
return GetStations().len() > 0;
}
function GetProduction() {
return AIIndustry.GetLastMonthProduction(industryID, cargoID);
}
function AcceptsCargo(cargoID) {
return AIIndustry.IsCargoAccepted(industryID, cargoID);
}
/**
* Returns an AITileList of tiles at which a road station can be built to pick up cargo.
*/
function GetPickupArea() {
return KeepBuildableArea(AITileList_IndustryProducing(industryID, TRUCK_STATION_RADIUS));
}
/**
* Returns an AITileList of tiles at which a road station can be built to deliver cargo.
*/
function GetDropoffArea() {
return KeepBuildableArea(AITileList_IndustryAccepting(industryID, TRUCK_STATION_RADIUS));
}
function _tostring() {
return GetName();
}
/**
* Create a list of all serviced cargo producing industries.
*/
static function FindServicedProducers() {
local industries = AIIndustryList();
local cargoes = AICargoList();
local producing = [];
for (local i = industries.Begin(); industries.HasNext(); i = industries.Next()) {
for (local c = cargoes.Begin(); cargoes.HasNext(); c = cargoes.Next()) {
local production = AIIndustry.GetLastMonthProduction(i, c);
if (production > 0) {
//Debug(AIIndustry.GetName(i) + " produces " + production + " units of " + AICargo.GetCargoLabel(c));
local industry = Industry(i, c);
if (industry.IsServiced()) producing.append(industry);
}
}
}
return producing;
}
/**
* Create a list of all cargo accepting industries.
*/
static function FindServicedConsumers() {
local industries = AIIndustryList();
local cargoes = AICargoList();
local accepting = [];
for (local i = industries.Begin(); industries.HasNext(); i = industries.Next()) {
for (local c = cargoes.Begin(); cargoes.HasNext(); c = cargoes.Next()) {
if (AIIndustry.IsCargoAccepted(i, c)) {
// Debug(AIIndustry.GetName(i) + " accepts " + AICargo.GetCargoLabel(c));
local industry = Industry(i, c);
if (industry.IsServiced()) accepting.append(industry);
}
}
}
return accepting;
}
}
class Station extends MapObject {
static stations = {}; // maps station IDs to Station instances
static function GetStation(stationID) {
return stationID in Station.stations ? Station.stations[stationID] : null;
}
stationID = 0;
destination = null;
/**
* Create a Station. We can't ask for the location of a
* competitor's station, so we use the tile we found it at.
*/
constructor(stationID, location, destination) {
MapObject.constructor(location);
this.stationID = stationID;
this.destination = destination;
Station.stations[stationID] <- this;
}
function GetStationID() {
return stationID;
}
function GetName() {
return AIStation.GetName(stationID);
}
function GetDestination() {
return destination;
}
function AcceptsCargo(cargoID) {
return AITile.GetCargoAcceptance(GetLocation(), cargoID, 1, 1, TRUCK_STATION_RADIUS) >= 8;
}
function _tostring() {
return stationID.tostring();
}
function IsOccupied() {
// check for vehicles currently loading at the station
local vehicles = AIVehicleList_Station(stationID);
vehicles.Valuate(AIVehicle.GetLocation);
vehicles.KeepValue(GetLocation());
vehicles.Valuate(AIVehicle.GetState);
vehicles.KeepValue(AIVehicle.VS_AT_STATION);
if (vehicles.Count() > 0) return true;
// check for vehicles on their way to load at the station
vehicles = AIVehicleList_Station(stationID);
vehicles.Valuate(AIOrder.ResolveOrderPosition, AIOrder.ORDER_CURRENT);
vehicles.KeepValue(0);
vehicles.Valuate(AIOrder.GetOrderDestination, AIOrder.ORDER_CURRENT);
vehicles.KeepValue(GetLocation());
vehicles.Valuate(DistanceValuator, GetLocation());
vehicles.KeepBelowValue(DEPOT_RANGE + 1);
return vehicles.Count() > 0;
}
function DistanceValuator(vehicle, stationTile) {
return AIMap.DistanceManhattan(AIVehicle.GetLocation(vehicle), stationTile);
}
}
class Depot extends MapObject {
// keep track of our depots by destination name
static depots = {}
static function GetDepot(destination) {
return destination.GetName() in Depot.depots ? Depot.depots[destination.GetName()] : null;
}
static function SetDepot(destination, depot) {
depots[destination.GetName()] <- depot;
}
constructor(location, destination) {
MapObject.constructor(location);
depots[destination.GetName()] <- this;
}
function BuildVehicle(cargoID) {
local vehicle = AIVehicle.BuildVehicle(location, GetBestEngine(cargoID));
AIVehicle.RefitVehicle(vehicle, cargoID);
return vehicle;
}
function CloneVehicle(vehicleID) {
return AIVehicle.CloneVehicle(location, vehicleID, true);
}
}
class Vehicle extends MapObject {
static vehicles = {}; // maps vehicle IDs to Vehicle instances
static function GetVehicle(vehicleID) {
return vehicleID in Vehicle.vehicles ? Vehicle.vehicles[vehicleID] : null;
}
vehicleID = 0;
route = null;
ageOffset = 0;
isSubsidyRunner = false;
headingForDepot = false;
hinUndWieder = false;
constructor(vehicleID, route) {
this.vehicleID = vehicleID;
this.route = route;
this.ageOffset = 0;
this.isSubsidyRunner = false;
this.headingForDepot = false;
this.hinUndWieder = false;
vehicles[vehicleID] <- this;
}
function GetName() {
return AIVehicle.GetName(vehicleID);
}
/**
* Returns the current destination of a vehicle.
*/
function GetCurrentDestination() {
return AIOrder.GetOrderDestination(vehicleID, AIOrder.ORDER_CURRENT);
}
function GoToDepot() {
if (headingForDepot) {
// already heading to depot
return true;
} else {
if (AIVehicle.SendVehicleToDepot(vehicleID)) {
headingForDepot = true;
return true;
}
}
}
function IsHeadingForDepot() {
return headingForDepot;
}
/**
* A vehicle is a bus if it holds passengers.
*/
function IsBus() {
return AIVehicle.GetCapacity(vehicleID, PASSENGERS) > 0;
}
/**
* A vehicle is at its destination if its location is the same as its second order's destination.
*/
function IsAtDestination() {
return AIVehicle.GetLocation(vehicleID) == AIOrder.GetOrderDestination(vehicleID, 1);
}
/**
* A vehicle is loading if it is VS_AT_STATION at its first order's destination.
*/
function IsLoading() {
return AIVehicle.GetLocation(vehicleID) == AIOrder.GetOrderDestination(vehicleID, 0) &&
AIVehicle.GetState(vehicleID) == AIVehicle.VS_AT_STATION;
}
/**
* A vehicle is loading if it is VS_AT_STATION at its second order's destination.
*/
function IsUnloading() {
return AIVehicle.GetLocation(vehicleID) == AIOrder.GetOrderDestination(vehicleID, 1) &&
AIVehicle.GetState(vehicleID) == AIVehicle.VS_AT_STATION;
}
/**
* Set the number of days to subtract from the vehicle's age when selling it.
*/
function SetAgeOffset(ageOffset) {
this.ageOffset = ageOffset;
}
function SetHinUndWieder(hinUndWieder) {
this.hinUndWieder = hinUndWieder;
local loadFlag = hinUndWieder ? AIOrder.AIOF_NONE : AIOrder.AIOF_NO_LOAD;
AIOrder.SetOrderFlags(vehicleID, 1, loadFlag | AIOrder.AIOF_NON_STOP_INTERMEDIATE);
}
function IsHinUndWieder() {
return hinUndWieder;
}
function Sell() {
local route = GetRoute();
if (route && !isSubsidyRunner) {
local age = AIVehicle.GetAge(vehicleID) - ageOffset;
local vehicleCost = AIEngine.GetPrice(AIVehicle.GetEngineType(vehicleID)) - AIVehicle.GetCurrentValue(vehicleID);
local profit = AIVehicle.GetProfitThisYear(vehicleID) + AIVehicle.GetProfitLastYear(vehicleID) - vehicleCost;
//Debug("Update " + route + ": triptime = " + age + ", profit = " + profit.tofloat()/age + " G/day");
// can't happen, but I do see routes with infinite value, so check for zero age -- Michiel
if (age > 0) route.Update(age, profit.tofloat()/age);
}
local sold = AIVehicle.SellVehicle(vehicleID);
if (sold) vehicles[vehicleID] <- null;
return sold;
}
/**
* Find this vehicle's route in the current list of routes.
*/
function GetRoute() {
return route;
}
/**
* Return whether the vehicle is currently empty.
*/
function IsEmpty() {
local list = AICargoList();
for (local cargoID = list.Begin(); list.HasNext(); cargoID = list.Next()) {
if (AIVehicle.GetCargoLoad(vehicleID, cargoID) > 0) return false;
}
return true;
}
/**
* Return whether the vehicle is currently full.
*/
function IsFull() {
local list = AICargoList();
for (local cargoID = list.Begin(); list.HasNext(); cargoID = list.Next()) {
if (AIVehicle.GetCargoLoad(vehicleID, cargoID) < AIVehicle.GetCapacity(vehicleID, cargoID)) return false;
}
return true;
}
}
rondje/info.nut 0000640 0063040 0023565 00000002657 11511076564 013100 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* Copyright 2008-2009 Marnix Bakker, Willem de Neve, Michiel Konstapel and Otto Visser.
* Suggestions/comments and bugs can go to: rondjeomdekerk@konstapel.nl
*/
class Rondje extends AIInfo {
function GetAuthor() { return "Rondje om de kerk"; }
function GetName() { return "Rondje"; }
function GetDescription() { return "Rondje om de kerk: a dirty, dirty AI"; }
function GetVersion() { return 384; }
function GetDate() { return "2008-02-24"; } // date of first public release
function CreateInstance() { return "Rondje"; }
function GetShortName() { return "ROND"; }
function UseAsRandomAI() { return false; }
function GetAPIVersion() { return "1.0"; }
}
RegisterAI(Rondje());
rondje/util.nut 0000640 0063040 0023565 00000017166 11410103411 013077 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* Copyright 2008-2009 Marnix Bakker, Willem de Neve, Michiel Konstapel and Otto Visser.
* Suggestions/comments and bugs can go to: rondjeomdekerk@konstapel.nl
*/
/**
* Return the entry of an item in an array, or -1 if not found.
*/
function IndexOf(list, item) {
foreach (index, entry in list) {
if (entry == item) return index;
}
return -1;
}
/**
* Calculates an integer square root.
*/
function Sqrt(i) {
if (i == 0)
return 0; // Avoid divide by zero
local n = (i / 2) + 1; // Initial estimate, never low
local n1 = (n + (i / n)) / 2;
while (n1 < n) {
n = n1;
n1 = (n + (i / n)) / 2;
}
return n;
}
/**
* Return the minimum of three numbers.
*/
function Min3(a, b, c) {
if (a < b && a < c) return a;
if (b < c) return b;
return c;
}
/**
* Find the cargo ID for passengers.
* Otto: newgrf can have tourist (TOUR) which qualify as passengers but townfolk won't enter the touristbus...
* hence this rewrite; you can check for PASS as string, but this is discouraged on the wiki
*/
function GetPassengerCargoID() {
local list = AICargoList();
local candidate = -1;
for (local i = list.Begin(); list.HasNext(); i = list.Next()) {
if (AICargo.HasCargoClass(i, AICargo.CC_PASSENGERS))
candidate = i;
}
if(candidate != -1)
return candidate;
throw "no passenger cargo in this game!";
}
/**
* (Re-)initialize the list of engines.
*/
function InitEngines() {
::bestEngines <- {};
}
/**
* Find the best (largest) engine for a given cargo ID.
*/
function GetBestEngine(cargoID) {
if (!(cargoID in bestEngines)) {
local engines = AIEngineList(AIVehicle.VT_ROAD);
engines.Valuate(AIEngine.CanRefitCargo, cargoID)
engines.KeepValue(1);
engines.Valuate(AIEngine.GetRoadType);
engines.KeepValue(AIRoad.ROADTYPE_ROAD);
engines.Valuate(AIEngine.GetCapacity);
engines.KeepTop(1);
bestEngines[cargoID] <- engines.Begin();
}
return bestEngines[cargoID];
}
/**
* Return the sum of a vehicle's profit over the last year and the current year.
*/
function GetVehicleProfit(vehicleID) {
return AIVehicle.GetProfitThisYear(vehicleID) + AIVehicle.GetProfitLastYear(vehicleID);
}
function MaxLoan() {
// since we can't (accidentally) spend money that's not in our bank balance,
// keep enough available in the form of loanable money to avoid bankrupcy
local safetyIntervals = Ceiling(GetMinimumSafeMoney().tofloat()/AICompany.GetLoanInterval());
local me = AICompany.ResolveCompanyID(AICompany.COMPANY_SELF);
if (AICompany.GetBankBalance(me) < 125000)
AICompany.SetLoanAmount(AICompany.GetMaxLoanAmount() - safetyIntervals * AICompany.GetLoanInterval());
}
/**
* Max out our loan, including the amount kept in reserve for paying station maintenance.
* Make sure you don't spend it!
*/
function FullyMaxLoan() {
AICompany.SetLoanAmount(AICompany.GetMaxLoanAmount());
}
function ManageLoan() {
// repay loan
// if we dip below our MinimumSafeMoney, we'll extend the loan up to its maximum,
// but the AI must take care not to spend this extra cash!
local me = AICompany.ResolveCompanyID(AICompany.COMPANY_SELF);
local balance = AICompany.GetBankBalance(me) - GetMinimumSafeMoney();
local balanceMod = (balance / AICompany.GetLoanInterval()) * AICompany.GetLoanInterval();
local loan = AICompany.GetLoanAmount();
if (balance < 0) {
// not good... we lost money?
FullyMaxLoan();
balance = AICompany.GetBankBalance(me) - GetMinimumSafeMoney();
balanceMod = (balance / AICompany.GetLoanInterval()) * AICompany.GetLoanInterval();
loan = AICompany.GetLoanAmount();
}
if (loan > 0 && balanceMod > 0) {
if (balanceMod >= loan) {
AICompany.SetLoanAmount(0);
} else {
AICompany.SetLoanAmount(loan - balanceMod);
}
}
}
function GetAvailableMoney() {
// how much we have, plus how much we can borrow
local me = AICompany.ResolveCompanyID(AICompany.COMPANY_SELF);
return AICompany.GetBankBalance(me) + AICompany.GetMaxLoanAmount() - AICompany.GetLoanAmount();
}
/**
* If this is the month before a bankrupcy check (March, June, September, December),
* keep enough cash around to pay for station maintenance.
* In other months, feel free to spend what we have.
*/
function GetMinimumSafeMoney() {
local date = AIDate.GetCurrentDate();
local month = AIDate.GetMonth(date);
if (month % 3 == 0) {
local safe = SAFETY_MARGIN;
safe += (AIStationList(AIStation.STATION_ANY).Count() * MONTHLY_STATION_MAINTENANCE);
// this is of course just a guesstimate, as the amount of vehicles constantly fluctuates
safe += (AIVehicleList().Count() * MONTHLY_STATION_MAINTENANCE); // TODO get cost from a vehicle(engine)
return safe;
} else {
return 0;
}
}
/**
* Add a rectangular area to an AITileList containing tiles that are within /radius/
* tiles from the center tile, taking the edges of the map into account.
*/
function SafeAddRectangle(list, tile, radius) {
local x1 = max(0, AIMap.GetTileX(tile) - radius);
local y1 = max(0, AIMap.GetTileY(tile) - radius);
local x2 = min(AIMap.GetMapSizeX() - 2, AIMap.GetTileX(tile) + radius);
local y2 = min(AIMap.GetMapSizeY() - 2, AIMap.GetTileY(tile) + radius);
list.AddRectangle(AIMap.GetTileIndex(x1, y1),AIMap.GetTileIndex(x2, y2));
}
/**
* Filter an AITileList for AITile.IsBuildable tiles.
*/
function KeepBuildableArea(area) {
area.Valuate(AITile.IsBuildable);
area.KeepValue(1);
return area;
}
/**
* Create an array from an AIList.
*/
function ListToArray(l) {
local a = [];
for (local item = l.Begin(); l.HasNext(); item = l.Next()) a.append(item);
return a;
}
/**
* Create an AIList from an array.
*/
function ArrayToList(a) {
local l = AIList();
foreach (item in a) l.AddItem(item, 0);
return l;
}
/**
* Create a string of all elements of an array, separated by a comma.
*/
function ArrayToString(a) {
local s = "";
foreach (index, item in a) {
if (index > 0) s += ", ";
s += item;
}
return s;
}
/**
* Return the closest integer equal to or greater than x.
*/
function Ceiling(x) {
if (x.tointeger().tofloat() == x) return x.tointeger();
return x.tointeger() + 1;
}
/**
* Remove a trailing \0 character from the end of a string.
* These occur after town names containing accented characters.
*/
function RemoveTrailingNull(s) {
if (s == null) return null;
local lastChar = s.slice(-1)[0];
return (lastChar == 0) ? s.slice(0, -1) : s;
}
function Debug(s) {
AILog.Info(GetDate() + ": " + s);
}
function Warning(s) {
AILog.Warning(GetDate() + ": " + s);
}
function Error(s) {
AILog.Error(GetDate() + ": " + s);
}
function GetTick() {
return ::INSTANCE.GetTick();
}
function GetDate() {
local date = AIDate.GetCurrentDate();
return AIDate.GetYear(date) + "/" + AIDate.GetMonth(date) + "/" + AIDate.GetDayOfMonth(date);
}
function PrintError() {
AILog.Error(AIError.GetLastErrorString());
}
rondje/main.nut 0000640 0063040 0023565 00000130067 11511100422 013043 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* Copyright 2008-2009 Marnix Bakker, Willem de Neve, Michiel Konstapel and Otto Visser.
* Suggestions/comments and bugs can go to: rondjeomdekerk@konstapel.nl
*/
require("util.nut");
require("world.nut");
require("RoadFinder/ConnectedChecker.nut");
const NAME = "Rondje Om De Kerk";
const DAYS_PER_YEAR = 365;
const MIN_DISTANCE = 10;
const MAX_DISTANCE = 256;
const NEW_ROUTE_MONEY_REQUIRED = 10000; // TODO still tweaking this (not changing this before the challenge)
const MAX_DROPOFF_VEHICLES = 20; // 10-20 is about right, don't go too high
const VEHICLE_MANAGEMENT_INTERVAL = 15; // ticks
const MAP_INTERVAL = 1000; // turns
const DEPOT_RANGE = 15; // range in which to build a depot for a station
const NUM_ROUTES_TO_STOP_MAPPING = 500; // when more than this many routes are found, stop mapping
const NUM_ROUTES_TO_STOP_EXPLORING = 200; // when more than this many routes have a confirmed profit, stop trying unknown routes
// when we have more money than this, send a vehicle instead of using the pathfinder
const MAX_PATHFINDER_MONEY = 200000;
const MONTHLY_STATION_MAINTENANCE = 50; // station upkeep per month
// TODO: make the safety margin dynamic; ie: dependent on amount of real estate and vehicles
const SAFETY_MARGIN = 2500; // extra money to keep around for bankrupcy checks
const MAX_PATHFINDING_TICKS = 500;
enum Districts {
CENTER
NORTH
SOUTH
WEST
EAST
};
enum RouteBuildingResult {
ROUTE_TOO_SHORT
ROUTE_TOO_LONG
ROUTE_NO_PROFIT
ROUTE_TOO_SOON
ROUTE_NOT_ENOUGH_CASH
ROUTE_LONGER_THAN_EXPECTED
ROUTE_BUILDING_FAILED
ROUTE_BUILT
};
enum VehicleBuildingResult {
NOT_ENOUGH_CASH
NOT_ENOUGH_TIME
ROUTE_JAMMED
DESTINATION_TOO_CROWDED
PICKUP_OCCUPIED
CARGO_NOT_ACCEPTED
NO_VEHICLES_BUILT
VEHICLES_BUILT
};
class Rondje extends AIController {
TESTING_vehiclesBuilt = 0;
TESTING_vehiclesSent = 0;
TESTING_vehiclesSold = 0;
world = null;
turn = 0;
//startEndgame = 0;
//endgameCheck = 0; // variable which will replace startEndgame
//endgameDate = 0;
lastUpdate = 0; // tick at which we last did a ManageVehicles
//endgameTiles = null; // tiles on which we can build stations during endgame
//cheapTilesCount = 0;
averageRouteValue = 0;
vehiclesAtStartEndgame = 0; // for determining the percentage of vehicles left before endgame.
routeList = []; // the unsorted list of routes generated during mapping
routeIndex = null; // a sorted AIList that indexes into routeList
currentRoute = 0; // index into routeIndex
explore = true; // try out new routes
map = true; // periodically map the world
forceRemap = true; // a flag indicating we should map the world again on the next turn
sort = false; // a flag indicating we should create a new routeIndex
report = false; // a flag indicating we should print out routes as we process them
analyze = false; // re-analyze the route list
turnsWithoutBuilding = 0; // number of times we went through the route processing loop without building a new route
buildNewRouteNextTurn = true; // allow or prohibit building a new route on the next turn
HQArea = null; // area options for HQ
prebuildRoutes = null;
function constructor() {
world = World();
prebuildRoutes = AIList();
InitEngines();
local cargoList = AICargoList();
for (local cargo = cargoList.Begin(); cargoList.HasNext(); cargo = cargoList.Next()) {
GetBestEngine(cargo);
}
::PASSENGERS <- GetPassengerCargoID();
::INSTANCE <- this;
::BUS_STATION_RADIUS <- AIStation.GetCoverageRadius(AIStation.STATION_BUS_STOP);
::TRUCK_STATION_RADIUS <- AIStation.GetCoverageRadius(AIStation.STATION_TRUCK_STOP);
::MAX_VEHICLES <- AIGameSettings.IsValid("max_roadveh") ? AIGameSettings.GetValue("max_roadveh") : 500;
// FindEndgameTiles();
// Find biggest town for HQ
local towns = AITownList();
towns.Valuate(AITown.GetPopulation);
towns.Sort(AIAbstractList.SORT_BY_VALUE, false);
local town = towns.Begin();
// Find empty 2x2 square as close to town centre as possible
local maxRange = Sqrt(AITown.GetPopulation(town)/100) + 5; //TODO check value correctness
HQArea = AITileList();
HQArea.AddRectangle(AITown.GetLocation(town) - AIMap.GetTileIndex(maxRange, maxRange), AITown.GetLocation(town) + AIMap.GetTileIndex(maxRange, maxRange));
HQArea.Valuate(AITile.IsBuildableRectangle, 2, 2);
HQArea.KeepValue(1);
HQArea.Valuate(AIMap.DistanceManhattan, AITown.GetLocation(town));
HQArea.Sort(AIList.SORT_BY_VALUE, true);
AIRoad.SetCurrentRoadType(AIRoad.ROADTYPE_ROAD);
}
function Start() {
NameCompany();
::START_DATE <- AIDate.GetCurrentDate();
::TICKS_PER_DAY <- TicksPerDay();
Debug("Max vehicles: " + MAX_VEHICLES);
local year = AIDate.GetYear(START_DATE);
// connected map scanning
local townlist = AITownList();
townlist.Valuate(AITown.GetPopulation);
townlist.Sort(AIList.SORT_BY_VALUE, false);
local townlist2 = AITownList();
local maxTowns = 10;
for (local startTown = townlist.Begin(); townlist.HasNext() && maxTowns--; startTown = townlist.Next()) {
for (local endTown = townlist2.Begin(); townlist2.HasNext(); endTown = townlist2.Next()) {
if (startTown == endTown || AIMap.DistanceManhattan(AITown.GetLocation(startTown), AITown.GetLocation(endTown)) > 150)
continue;
local max_cost = 3*AIMap.DistanceManhattan(AITown.GetLocation(startTown), AITown.GetLocation(endTown));
local pathfinder = ConnectedChecker(max_cost);
//pathfinder.cost.max_cost = 2*(AIMap.GetMapSizeX() + AIMap.GetMapSizeY());
pathfinder.InitializePath([AITown.GetLocation(startTown)], [AITown.GetLocation(endTown)]);
local path = false;
while (path == false) {
path = pathfinder.FindPath(-1);
}
if (path != null) {
Debug("W00tNess!!! there is pre-connected towns: " + AITown.GetName(startTown) + " <--> " + AITown.GetName(endTown));
// maxTowns = 10; // either we started later or there's prebuild stuff: do more searching
prebuildRoutes.AddItem(startTown, AITown.GetPopulation(startTown));
prebuildRoutes.AddItem(endTown, AITown.GetPopulation(endTown));
}
}
}
BuildHQ(HQArea);
// endgameDate = AIDate.GetDate(year + 10, 1, 1);//may need to become + 9, 12, 31 or + 9, 12, 30... uncertain about that.
// endgameCheck = AIDate.GetDate(year + 8, 2, 1);//first check in february 2006.
// startEndgame = AIDate.GetDate(year + 9, 12, 1);//always start if there is less than a month to go.
// local eday = AIDate.GetDayOfMonth(endgameCheck);
// local emonth = AIDate.GetMonth(endgameCheck);
// local eyear = AIDate.GetYear(endgameCheck);
// Debug("End of game at: " + AIDate.GetDayOfMonth(endgameDate) + "-"+AIDate.GetMonth(endgameDate) + "-"+AIDate.GetYear(endgameDate));
// Debug("First endgamecheck will be at date: " + eday + "-" + emonth + "-" + eyear + ".");
// Debug("Total number of stations that can be prebuild: " + prebuildRoutes.Count());
for (local station = prebuildRoutes.Begin(); prebuildRoutes.HasNext(); station = prebuildRoutes.Next()) {
buildPassengerStation(station);
}
ManageLoan();
Debug("Started, scanning...");
while (true) {
local bigTick = GetTick();
TESTING_vehiclesSent = 0;
TESTING_vehiclesSold = 0;
TESTING_vehiclesBuilt = 0;
try {
/* if (AIDate.GetCurrentDate() >= endgameCheck) {
local nextCheck = CheckEndgame(endgameDate);
// Debug("endgame check returned: " + nextCheck);
switch (nextCheck) {
case 0:
startEndgame = AIDate.GetCurrentDate();
vehiclesAtStartEndgame = AIVehicleList().Count(); // for determining the percentage of vehicles left before endgame.
break;
case 1:
endgameCheck += AIDate.GetDate(0, 1, 2);
break;
case 2:
endgameCheck += AIDate.GetDate(0, 1, 3);
break;
case 3:
endgameCheck += AIDate.GetDate(0, 1, 5);
break;
case 4:
endgameCheck += AIDate.GetDate(0, 1, 11);
break;
case 5:
endgameCheck += AIDate.GetDate(0, 1, 21);
break;
case 6:
endgameCheck += AIDate.GetDate(0, 2, 1);
break;
case 7:
endgameCheck += AIDate.GetDate(0, 2, 15);
break;
case 8:
endgameCheck += AIDate.GetDate(0, 3, 1);
break;
}
eday = AIDate.GetDayOfMonth(endgameCheck);
emonth = AIDate.GetMonth(endgameCheck);
eyear = AIDate.GetYear(endgameCheck);
Debug("next endgamecheck will be at date: " + eday + "-" + emonth + "-" + eyear + ".");
} */
// endgame disabled; uncomment to enable
// if (AIDate.GetCurrentDate() < startEndgame) {
local tick;
CheckEvents();
ManageVehicles();
ManageLoan();
if (map && (forceRemap || turn % MAP_INTERVAL == 0)) {
MapWorld();
}
if (sort) {
sort = false;
tick = GetTick();
routeIndex = AIList();
foreach (i, route in routeList) {
if (!explore && !route.IsValueConfirmed()) continue;
routeIndex.AddItem(i, route.GetRouteValue().tointeger());
}
routeIndex.Sort(AIList.SORT_BY_VALUE, false);
report = true;
tick = GetTick() - tick;
if (tick > 20) Warning("Sorting took " + tick + " ticks");
}
if (analyze) {
tick = GetTick();
AnalyzeRouteList();
tick = GetTick() - tick;
if (tick > 20) Warning("Analyzing routes took " + tick + " ticks");
}
tick = GetTick();
local t;
local manageVehiclesTime = 0;
local buildVehiclesTime = 0;
local buildRoutesTime = 0;
local processedPickups = {};
local buildNewRoutes = buildNewRouteNextTurn && explore;
local builtRoute = false;
buildNewRouteNextTurn = true;
MaxLoan();
for (local i = routeIndex.Begin(); routeIndex.HasNext(); i = routeIndex.Next()) {
/*if (AIDate.GetCurrentDate() > endgameCheck) {
// see if it's endgame time
break;
}*/
if (GetAvailableMoney() <= GetMinimumSafeMoney()) {
// max out our loan to provide the cash for station maintenance
// and stop spending so we don't get declared bankrupt
FullyMaxLoan();
break;
}
local route = routeList[i];
// routes can disappear after mapping, since industries can close down
if (!route.IsValid()) {
continue;
}
// don't consider routes that don't make a profit
if (route.GetRouteValue() <= 0) {
// everything else will be even worse
break;
}
if (route.IsBuilt()) {
// if we have sent vehicles from A to B, don't bother considering A to C, D, E...
if (route.GetPickup() in processedPickups) {
continue;
}
t = GetTick();
local result = AddVehicles(route);
if (result == VehicleBuildingResult.NOT_ENOUGH_CASH) {
// no money to spare
// don't try to build a new route next turn
buildNewRouteNextTurn = false;
// don't try to build vehicles on routes that are worse
break;
} else if (result == VehicleBuildingResult.VEHICLES_BUILT) {
// still room left on current routes
// don't try to build a new route next turn
buildNewRouteNextTurn = false;
processedPickups[route.GetPickup()] <- true;
} else {
// don't care, next!
}
buildVehiclesTime += GetTick() - t;
}
else if (buildNewRoutes && route.IsBuildable()) {
t = GetTick();
local result = ConsiderBuildingRoute(route);
if (result == RouteBuildingResult.ROUTE_NOT_ENOUGH_CASH) {
// stop building routes this time around, because we don't want to spend our money
// on worse routes, but keep building vehicles or we might run out of money
buildNewRoutes = false;
} else if (result == RouteBuildingResult.ROUTE_BUILT || result == RouteBuildingResult.ROUTE_LONGER_THAN_EXPECTED) {
// only try to build one route per loop, because building one route may connect others
// (especially towns) and we don't want unnecessary pathfinding
// and we need to keep pumping out vehicles
buildNewRoutes = false;
analyze = true;
if (result == RouteBuildingResult.ROUTE_BUILT) {
builtRoute = true;
processedPickups[route.GetPickup()] <- true;
}
} else if (result == RouteBuildingResult.ROUTE_NO_PROFIT) {
// the rest is going to be even worse, so don't bother
break;
} else {
// too short, too long, no profit, couldn't build: continue with the next route
}
buildRoutesTime += GetTick() - t;
}
t = GetTick();
ManageVehicles();
manageVehiclesTime += GetTick() - t;
}
tick = GetTick() - tick;
if (tick > 20) {
Warning("Processing routes took " + tick + " ticks, of which " +
manageVehiclesTime + " for managing vehicles " +
"(" + TESTING_vehiclesSent + " sent, " + TESTING_vehiclesSold + " sold), " +
buildVehiclesTime + " for building " + TESTING_vehiclesBuilt + " vehicles, " +
buildRoutesTime + " for building routes");
}
// keep track of whether we've built anything
// if not, we may need to search for new routes
if (buildNewRoutes && !builtRoute) {
turnsWithoutBuilding++;
} else {
turnsWithoutBuilding = 0;
}
// TODO: a better critirion? (not changing this before the game)
// map and search for new routes if we have money left and didn't build a route on the last N passes
if (map && turnsWithoutBuilding > 20 && GetAvailableMoney() > 2*NEW_ROUTE_MONEY_REQUIRED) {
// we need more routes!
turnsWithoutBuilding = 0;
forceRemap = true;
}
// } else {
// BuildStations();
// }
ManageVehicles();
ManageLoan();
turn++;
if (bigTick == GetTick()) {
Sleep(1);
}
} catch (e) {
AILog.Error("Exception caught:");
AILog.Error(e);
}
bigTick = GetTick() - bigTick;
if (bigTick > 50) Warning("Main loop took " + bigTick + " ticks");
}
}
function getRoadTile(t) {
local adjacent = AITileList();
adjacent.AddTile(t - AIMap.GetTileIndex(1,0));
adjacent.AddTile(t - AIMap.GetTileIndex(0,1));
adjacent.AddTile(t - AIMap.GetTileIndex(-1,0));
adjacent.AddTile(t - AIMap.GetTileIndex(0,-1));
adjacent.Valuate(AIRoad.IsRoadTile);
adjacent.KeepValue(1);
adjacent.Valuate(AIRoad.IsRoadDepotTile);
adjacent.KeepValue(0);
adjacent.Valuate(AIRoad.IsRoadStationTile);
adjacent.KeepValue(0);
if (adjacent.Count())
return adjacent.Begin();
else
return null;
}
function buildPassengerStation(town) {
Debug("Building station in " + AITown.GetName(town));
// Find empty square as close to town centre as possible
local spotFound = false;
local curRange = 1;
local maxRange = Sqrt(AITown.GetPopulation(town)/100) + 2;
local area = AITileList();
while (curRange < maxRange) {
//AILog.Info("looking with range " + curRange);
area.AddRectangle(AITown.GetLocation(town) - AIMap.GetTileIndex(curRange, curRange), AITown.GetLocation(town) + AIMap.GetTileIndex(curRange, curRange));
area.Valuate(AIRoad.IsRoadTile);
area.KeepValue(1);
area.Valuate(AIRoad.IsDriveThroughRoadStationTile);
area.KeepValue(0);
area.Valuate(AIRoad.GetNeighbourRoadCount);
area.KeepValue(2); // entrance and exit; allow 1 as well?
if (area.Count()) {
//AILog.Info("Found " + area.Count() + " possible options");
for (local t = area.Begin(); area.HasNext(); t = area.Next()) {
local opening = getRoadTile(t);
if(opening) {
// AILog.Info("tile " + t + " has opening " + opening);
if (/*AIRoad.BuildRoad(opening, t) &&*/ AIRoad.BuildDriveThroughRoadStation(t, opening, AIRoad.ROADVEHTYPE_BUS, AIStation.STATION_JOIN_ADJACENT)) {
//AISign.BuildSign(t, ("bus " + AITown.GetName(town)));
return t;
}
if(AIError.GetLastError() == AIRoad.ERR_ROAD_CANNOT_BUILD_ON_TOWN_ROAD)
return buildNonInlinePassengerStation(town);
AILog.Info("Error building passenger station " + AIError.GetLastErrorString());
//AISign.BuildSign(t, AIError.GetLastErrorString());
} //else {
// AILog.Info("tile" + t + " has no opening");
//}
}
curRange++;
} else {
curRange++;
}
}
AILog.Info("No possible station location found");
return null;
}
function buildNonInlinePassengerStation(town) {
Debug("Building non-inline station as it's not allowed to build on town roads...");
// Find empty square as close to town centre as possible
local spotFound = false;
local curRange = 1;
local maxRange = Sqrt(AITown.GetPopulation(town)/100) + 4; // search larger area
local area = AITileList();
while (curRange < maxRange) {
//Debug("looking with range " + curRange);
area.AddRectangle(AITown.GetLocation(town) - AIMap.GetTileIndex(curRange, curRange), AITown.GetLocation(town) + AIMap.GetTileIndex(curRange, curRange));
area.Valuate(AITile.IsBuildable);
area.KeepValue(1);
if (area.Count()) {
//Debug("Found " + area.Count() + " possible options");
for (local t = area.Begin(); area.HasNext(); t = area.Next()) {
local opening = getRoadTile(t);
if(opening) {
// Debug("tile " + t + " has opening " + opening);
if (AIRoad.BuildRoad(opening, t) && AIRoad.BuildRoadStation(t, opening, AIRoad.ROADVEHTYPE_BUS, AIStation.STATION_JOIN_ADJACENT)) {
//AISign.BuildSign(t, ("bus " + AITown.GetName(town)));
return t;
}
Error("Error building non-inline passenger station " + AIError.GetLastErrorString());
//AISign.BuildSign(t, "" + AIRoad.GetNeighbourRoadCount(t));
// Can this actually happen or is this bad copy paste work??
if(AIError.GetLastError() == AIRoad.ERR_ROAD_CANNOT_BUILD_ON_TOWN_ROAD)
return buildNonInlinePassengerStation(town);
} //else {
// Debug("tile" + t + " has no opening");
//}
}
curRange++;
} else {
curRange++;
}
}
Debug("No possible station location found");
return null;
}
function MapWorld() {
Debug("Mapping the world...");
forceRemap = false;
sort = true;
analyze = true;
local tick = GetTick();
world.Map();
routeList = world.GetRouteList();
tick = GetTick() - tick;
if (tick > 20) Warning("Mapping took " + tick + " ticks");
}
function TileValuator(tile) {
local value = 247;
if (AITile.HasTreeOnTile(tile))
value += 66; // can't determine how many trees there are, so assume max
if (AITile.IsFarmTile(tile))
value += 540;
if (AITile.IsRockTile(tile))
value += 203;
if (AITile.IsRoughTile(tile))
value += 23;
if (AITile.IsSnowTile(tile))
value += 23;
if (AITile.IsDesertTile(tile))
value += 23;
if (AITile.IsCoastTile(tile))
value += 123;
if (AITile.GetSlope(tile))
value += 281; // NOTE: needs finding correct orientation, or loop with 4 orientations if fails
if (value == 247)
INSTANCE.cheapTilesCount++;
return value;
}
/**
* Process game events.
*/
function CheckEvents() {
while (AIEventController.IsEventWaiting()) {
local e = AIEventController.GetNextEvent();
local converted;
switch (e.GetEventType()) {
case AIEvent.AI_ET_VEHICLE_UNPROFITABLE:
converted = AIEventVehicleUnprofitable.Convert(e);
Warning("Vehicle unprofitable: " + AIVehicle.GetName(converted.GetVehicleID()));
local vehicle = Vehicle.GetVehicle(converted.GetVehicleID());
if (!vehicle) break;
// VerifyRoutes() can take a VERY long time, so don't do this for potentially
// many vehicles! Just send them to a depot.
vehicle.GoToDepot();
//local route = vehicle.GetRoute();
//if (route && route.IsConnected()) {
// // seems to be OK? maybe just a long route or a jam
//} else {
// // route is broken, VerifyRoutes to send others to depot
// VerifyRoutes();
//}
break;
case AIEvent.AI_ET_VEHICLE_LOST:
converted = AIEventVehicleLost.Convert(e);
Warning("Vehicle lost: " + AIVehicle.GetName(converted.GetVehicleID()) + ", sending to depot");
local vehicle = Vehicle.GetVehicle(converted.GetVehicleID());
if (vehicle) vehicle.GoToDepot();
break;
case AIEvent.AI_ET_COMPANY_IN_TROUBLE:
converted = AIEventCompanyInTrouble.Convert(e);
if (converted.GetCompanyID() == AICompany.COMPANY_SELF) {
Warning("!!! We're in money trouble !!!");
// TODO: feed this to getminimumsafemoney function, so we
// can be extra extra careful for a while.
}
break;
case AIEvent.AI_ET_COMPANY_BANKRUPT:
// we may have been using their tunnels/bridges, which are now gone
// if we're not too far into the game, verify
// else, just let it slide
Warning("A company went bankrupt; checking for side effects...");
//if (startEndgame - AIDate.GetCurrentDate() < 2*365) {
VerifyRoutes();
//} else {
// Warning("Too late to verify routes");
//}
break;
case AIEvent.AI_ET_ENGINE_AVAILABLE:
InitEngines();
break;
default:
// Debug("Unhandled event:" + e);
}
}
ManageLoan();
}
function AnalyzeRouteList() {
local count = 0;
local profitable = 0;
local built = 0;
local confirmed = 0;
local confirmedProfitable = 0;
local serviced = 0;
local totalRouteValue = 0;
for (local i = routeIndex.Begin(); routeIndex.HasNext(); i = routeIndex.Next()) {
local route = routeList[i];
count++;
//if (report) {
if (count < 26) Debug(count + ": " + route);
if (count == 26) Debug("... and " + (routeList.len() - count + 1) + " more");
//}
if (route.GetRouteValue() > 0) profitable++;
if (route.IsValueConfirmed()) confirmed++;
if (route.GetRouteValue() > 0 && route.IsValueConfirmed()) confirmedProfitable++;
if (route.IsBuilt()) built++;
if (route.GetNumberOfVehicles() > 0) serviced++;
if (route.GetRouteValue() > 0) {
// ignore unprofitable routes
totalRouteValue += route.GetRouteValue();
}
}
averageRouteValue = (profitable == 0) ? 0 : totalRouteValue / profitable;
Debug("Total/profitable/built/confirmed/conf.profitable/serviced number of routes: " +
routeList.len() + " / " + profitable + " / " + built + " / " + confirmed + " / " + confirmedProfitable + " / " + serviced);
Debug("Average profitable route value: " + averageRouteValue + " G/d");
if (count > NUM_ROUTES_TO_STOP_MAPPING) {
Warning(count + " routes found, no longer mapping");
map = false;
}
if (confirmedProfitable > NUM_ROUTES_TO_STOP_EXPLORING) {
Warning(confirmed + " confirmed profitable routes, no longer exploring");
explore = false;
}
report = false;
analyze = false;
}
/**
* Called during pauses in mapping and path finding, so we can send vehicles to depots and build new vehicles.
*/
function ManageVehicles() {
if (!AIVehicleList().IsEmpty()) {
if (GetTick() > lastUpdate + VEHICLE_MANAGEMENT_INTERVAL) {
lastUpdate = GetTick();
SendVehiclesToDepot();
SellVehiclesInDepot();
}
}
}
function VerifyRoutes() {
Debug("Verifying routes...");
local tick = GetTick();
MapWorld();
local routeNames = {};
foreach (route in routeList) {
routeNames[route.GetName()] <- true;
}
local vehicleIDs = AIVehicleList();
for (local vehicleID = vehicleIDs.Begin(); vehicleIDs.HasNext(); vehicleID = vehicleIDs.Next()) {
try {
local vehicle = Vehicle.GetVehicle(vehicleID);
if (vehicle) { // might have arrived in depot already, so check for NULL
if (vehicle.GetRoute().GetName() in routeNames) {
// OK
} else {
Warning(vehicle.GetName() + " has a broken route, sending to depot");
vehicle.GoToDepot();
}
}
} catch (e) {}
}
Debug("Verifying routes took " + (GetTick() - tick) + " ticks");
}
function SendVehiclesToDepot() {
// process vehicles currently at their dropoff station
// Not working anymore :-(
/* local vehicleIDs = AIVehicleList();
vehicleIDs.Valuate(AIVehicle.GetState);
vehicleIDs.KeepValue(AIVehicle.VS_AT_STATION);
vehicleIDs.Valuate(AIOrder.ResolveOrderPosition, AIOrder.ORDER_CURRENT);
vehicleIDs.KeepValue(1); // pickup -> dropoff -> depot
for (local vehicleID = vehicleIDs.Begin(); vehicleIDs.HasNext(); vehicleID = vehicleIDs.Next()) {
local vehicle = Vehicle.GetVehicle(vehicleID);
if (!vehicle.IsHeadingForDepot() && !vehicle.IsHinUndWieder() && vehicle.IsUnloading() && !vehicle.IsFull()) {
if (vehicle.GoToDepot()) {
TESTING_vehiclesSent++;
}
}
}*/
// process vehicles heading for their dropoff depot
local vehicleIDs = AIVehicleList();
vehicleIDs.Valuate(AIOrder.ResolveOrderPosition, AIOrder.ORDER_CURRENT);
vehicleIDs.KeepValue(2); // pickup -> dropoff -> depot
for (local vehicleID = vehicleIDs.Begin(); vehicleIDs.HasNext(); vehicleID = vehicleIDs.Next()) {
local vehicle = Vehicle.GetVehicle(vehicleID);
if (!vehicle.IsHeadingForDepot() && !vehicle.IsHinUndWieder() && vehicle.GoToDepot()) {
TESTING_vehiclesSent++;
}
}
}
function SellVehiclesInDepot() {
local vehicleIDs = AIVehicleList();
vehicleIDs.Valuate(AIVehicle.GetState);
vehicleIDs.KeepValue(AIVehicle.VS_IN_DEPOT);
if (vehicleIDs.Count() > 0) {
for (local vehicleID = vehicleIDs.Begin(); vehicleIDs.HasNext(); vehicleID = vehicleIDs.Next()) {
local vehicle = Vehicle.GetVehicle(vehicleID);
local route = vehicle.GetRoute();
local oldValue = route.GetRouteValue();
vehicle.Sell();
TESTING_vehiclesSold++;
local newValue = route.GetRouteValue();
local ratio = newValue.tofloat()/oldValue;
if (ratio > 2 || ratio < 0.5) {
Debug(route.GetName() + " changed value from " + oldValue + " to " + newValue + ", going to re-sort routes");
sort = true;
}
}
}
}
/**
* See if we should build more vehicles for this route.
*/
function AddVehicles(route) {
// see if we can pay for it
local engine = GetBestEngine(route.GetCargo());
if (AIEngine.GetPrice(engine) > GetAvailableMoney()) return VehicleBuildingResult.NOT_ENOUGH_CASH;
// see if the dropoff station isn't too crowded
local numDropoffVehicles = AIVehicleList_Station(route.GetDropoffStation().stationID).Count();
if (numDropoffVehicles >= MAX_DROPOFF_VEHICLES)
return VehicleBuildingResult.DESTINATION_TOO_CROWDED;
// don't build more vehicles on jammed routes
if (route.IsJammedOrBroken())
return VehicleBuildingResult.ROUTE_JAMMED;
// see if the vehicle still has time to make the trip before the end of the game
// local daysRemaining = startEndgame - AIDate.GetCurrentDate();
// if (route.GetTripTime() > daysRemaining)
// return VehicleBuildingResult.NOT_ENOUGH_TIME;
// see if the station still accepts this cargo
if(!route.GetDropoffStation().AcceptsCargo(route.GetCargo()))
return VehicleBuildingResult.CARGO_NOT_ACCEPTED;
// see if the pickup station is occupied
if (route.GetPickupStation().IsOccupied())
return VehicleBuildingResult.PICKUP_OCCUPIED;
// calculate the number of vehicles to add
local capacity = AIEngine.GetCapacity(engine);
local numNeeded = max(1, route.GetCargoWaiting() / capacity);
local toBuild = min(MAX_DROPOFF_VEHICLES - numDropoffVehicles, numNeeded);
local added;
for (added = 0; added < toBuild; added++) {
local vehicle = route.AddVehicle();
if (!vehicle) break;
// add a non-teleporting vehicle if:
// - we have lots of money
// - not too many vehicles,
// - room to spare at the dropoff
// but only on our worse-than-average routes (keep teleporting on the high profit ones)
if (added == 0 &&
GetAvailableMoney() > 500000 &&
!route.IsFreight() &&
AIVehicleList().Count() < MAX_VEHICLES - 50 &&
numDropoffVehicles < 0.75*MAX_DROPOFF_VEHICLES &&
route.GetRouteValue() < averageRouteValue) {
Debug("Added non-teleporter to " + route.GetName());
vehicle.SetHinUndWieder(true);
}
// it takes approximately 3 days to load a vehicle and get it out of the station,
// so don't penalize vehicles for waiting in line
// (which would lower the route value estimate when they arrive)
vehicle.SetAgeOffset(added * 3);
}
TESTING_vehiclesBuilt += added;
//if (added > 0) Debug("Added " + added + " vehicles to " + route);
return added > 0 ? VehicleBuildingResult.VEHICLES_BUILT : VehicleBuildingResult.NO_VEHICLES_BUILT;
}
/**
* If a route looks interesting, build stations, depots and vehicles for it.
* @return true if it was built, false otherwise
*/
function ConsiderBuildingRoute(route) {
if (route.GetDistance() < MIN_DISTANCE) {
return RouteBuildingResult.ROUTE_TOO_SHORT;
} else if (route.GetDistance() > MAX_DISTANCE) {
return RouteBuildingResult.ROUTE_TOO_LONG;
} else if (route.GetRouteValue() < 0) {
return RouteBuildingResult.ROUTE_NO_PROFIT;
} else if (GetAvailableMoney() < NEW_ROUTE_MONEY_REQUIRED + AIEngine.GetPrice(GetBestEngine(route.GetCargo()))) {
return RouteBuildingResult.ROUTE_NOT_ENOUGH_CASH;
} else if (IsFirstYear() && IsSuburb(route)) {
return RouteBuildingResult.ROUTE_TOO_SOON;
} else {
try {
local tick = GetTick();
// if we have lots of routes and lots of money, don't waste time with the pathfinder
if (GetAvailableMoney() < MAX_PATHFINDER_MONEY) {
// either we're short on routes or short on money (or both)
// so invest some ticks in pathfinding
Debug("Re-estimating route: " + route.GetName());
local estimatedDistance = route.GetDistance();
route.CalculateImprovedEstimate();
Debug("Re-estimating route took " + (GetTick() - tick) + " ticks");
if (route.GetDistance().tofloat()/estimatedDistance >= 1.5) {
// much longer - don't build the route so that it is revalued the next time around
Warning(route.GetName() + " is now estimated at " + route.GetDistance() + " tiles, instead of " + estimatedDistance);
Warning(route.GetName() + " is now valued at " + route.GetRouteValue() + " G/d");
sort = true;
return RouteBuildingResult.ROUTE_LONGER_THAN_EXPECTED;
}
} else {
// set the route value to 0 so we won't send any more vehicles until our scout vehicle arrives
// and confirms the route makes a profit
Debug("Sending scout vehicle on " + route);
route.SetRouteValue(0);
}
Debug("Building route: " + route);
tick = GetTick();
BuildRoute(route);
local vehicle = route.AddVehicle();
// for subsidized routes, send the first vehicle off as soon as it has a single unit of cargo
if (vehicle && route.IsSubsidized()) {
local ticks = 0;
// don't wait longer than a week
while (vehicle.IsEmpty() && ticks < 7*TICKS_PER_DAY) {
ticks++;
Sleep(1);
}
if (!vehicle.IsEmpty()) {
// it's almost empty, so it won't make a profit
// this flag prevents it from lowering the route value
vehicle.isSubsidyRunner = true;
// send it off
AIVehicle.SkipToVehicleOrder(vehicle.vehicleID, 1);
}
}
// make it prove itself: lower estimated route value
// it'll be replaced by the first real data point
route.SetRouteValue(route.GetRouteValueEstimate()/2);
Debug("Building route took " + (GetTick() - tick) + " ticks");
return RouteBuildingResult.ROUTE_BUILT;
} catch (e) {
Error("Could not build route " + route + ": " + e);
if (typeof(e) == "instance" && (e instanceof NoRoomForStationException || e instanceof NoRoomForDepotException || e instanceof PathfindingException || e instanceof PissedOffAuthorityException)) {
Debug("Marking as unbuildable");
route.SetBuildable(false);
}
return RouteBuildingResult.ROUTE_BUILDING_FAILED;
}
}
}
function IsFirstYear() {
return AIDate.GetCurrentDate() - START_DATE < DAYS_PER_YEAR;
}
function IsSuburb(route) {
// a suburb is any district other than the center
return route.GetPickup() instanceof District && route.GetPickup().GetDistrict() != Districts.CENTER;
}
/**
* Build stations until we run out of money, or tiles.
*/
function BuildStations() {
// don't re-valuate the list, that'll destroy the sort order!
// since each build takes a tick anyway, just test for trees inside the loop
// endgameTiles.Valuate(AITile.IsBuildable); // remove everything that has been built past 9-ish years
// endgameTiles.KeepValue(1);
// endgameTiles.Valuate(AITile.HasTreeOnTile); // remove new trees
// endgameTiles.KeepValue(0);
Debug("There are " + endgameTiles.Count() + " buildable tiles");
// at this point, we don't need to worry about bankrupcy
FullyMaxLoan();
foreach (id, vehicle in Vehicle.vehicles) {
if (vehicle) vehicle.SetHinUndWieder(false);
}
local count = 0;
local tile = endgameTiles.Begin();
while (endgameTiles.HasNext()) {
//local tickteller = AIController.GetTick();// for testing
/*/sell vehicles when we need money (anders verkoop je toch gewoon de boot?)
while (GetAvailableMoney() < 2500) {
local vehicles = AIVehicleList();
vehicles.Valuate(AIVehicle.IsStoppedInDepot);
vehicles.KeepValue(1);
// sell the most valuable ones first, since their value will drop the fastest.
vehicles.Valuate(AIVehicle.GetCurrentValue);
vehicles.Sort(AIList.SORT_BY_VALUE, false);
if (vehicles.IsEmpty()) {
// nothing to sell, wait and see if more vehicles arrive in a depot
SendVehiclesToDepot();
Sleep(1);
break;
} else {
local vehicle = vehicles.Begin();
Debug("Selling vehicle " + AIVehicle.GetName(vehicle) + " for " + AIVehicle.GetCurrentValue(vehicle));
AIVehicle.SellVehicle(vehicle);
}
//this part is commented out because we will now sell the vehicels as soon as we can.
}*/
/*// another sellvehicle setup, compatible with letting the vehicles run for as long as possible...
while (GetAvailableMoney() < 2500) {
local vehicles = AIVehicleList();
if (vehicles.IsEmpty()) break;
vehicles.Valuate(AIVehicle.IsStoppedInDepot);
vehicles.KeepValue(1);
if (vehicles.IsEmpty()) {
SendVehiclesToDepot();
} else {
SellVehiclesInDepot();
}
}*/
// skip tiles on which trees have grown, or stuff has been built
if (AITile.HasTreeOnTile(tile) || !AITile.IsBuildable(tile) || AITile.IsFarmTile(tile)) {
tile = endgameTiles.Next();
continue;
}
if (AIRoad.BuildDriveThroughRoadStation(tile, tile - 1, AIRoad.ROADVEHTYPE_TRUCK, AIStation.STATION_NEW)) {
count++;
}
if (AIError.GetLastError() == AIError.ERR_NOT_ENOUGH_CASH) {
// if we failed from lack of money, stay on this tile
} else {
tile = endgameTiles.Next();
}
if (count % VEHICLE_MANAGEMENT_INTERVAL == 0) {
SendVehiclesToDepot();
SellVehiclesInDepot();//added instead of selling the vehicles only when we need money
//beensellingvehicles = true;
}
//local tookticks = AIController.GetTick() - tickteller;
//Debug("total ticks are at: " + AIController.GetTick());
//Debug("this loop took " + tookticks + " ticks,");
//if (beensellingvehicles){
// Debug("And we have not been selling vehicles!");
//} else {
// Debug("But we were selling vehicles.");
//}
//beensellingvehicles = false;
/*if (AIDate.GetCurrentDate() >= endgameDate) {
// game over!
break;
}*/
}
// for determining the percentage of vehicles left before endgame.
Debug("Number of vehicles at start endgame: " + vehiclesAtStartEndgame + ".");
Debug("Number of vehicles at end of game: " + AIVehicleList().Count() + ".");
Debug("Percentage of vehicles left at end of game: " + ((AIVehicleList().Count() / (vehiclesAtStartEndgame + 1))*100) + ".");
}
function ClearSigns() {
for (local i=0; i 0; days = days - 30 - odd) {
//add the costs for building and upkeep for this moth.
costuntilend += (30 + odd) * TICKS_PER_DAY * (maxcostperstation + upkeep);
//if the month we are considering has already started, we will need to subtract the days which have already passed.
if (days < 30 + odd) {
local surplusdays = 30 + odd - days;
costuntilend -= surplusdays * TICKS_PER_DAY * (maxcostperstation + upkeep);
}
odd = 1 - odd;
upkeep += MONTHLY_STATION_MAINTENANCE;
}
Debug("Cost for building stations and maintenance (full): " + costuntilend);
local ourVehicles = AIVehicleList();
local vehicleCount = ourVehicles.Count();
local stationsNotBuilt = 2 * vehicleCount * maxcostperstation;//the building costs for the stations which can't be built because we're selling vehicles.
//the factor 2 is beacuse both the order to go to the depot and the selling cost a tick.
Debug("Cost until end, minus not built due to selling vehicles: " + costuntilend);
//calculate cost for maintenance of existing stations (will be subtracted).
local numberOfStations = AIStationList(AIStation.STATION_ANY).Count();
local monthsUntilEnd = (daysuntilend/30.5).tointeger();
local stationMaintenance = monthsUntilEnd * numberOfStations * MONTHLY_STATION_MAINTENANCE;
Debug("stationmaintenance: " + stationMaintenance);
//calculate vehicle running cost until enddate.
local runningCosts = 0;
local vehicleMoney = 0;
local vehicleIncome = 0;
local maintenancediscount = 0;
for(local vehicleID = ourVehicles.Begin(); ourVehicles.HasNext(); vehicleID = ourVehicles.Next()) {
local vehicle = Vehicle.GetVehicle(vehicleID);
if (vehicle && vehicle.GetRoute() && !vehicle.IsHinUndWieder()) {
local route = vehicle.GetRoute();
local triptimeleft = route.GetTripTime() - AIVehicle.GetAge(vehicleID);
if (triptimeleft < 1) triptimeleft = 1;
if (route.IsJammedOrBroken()) triptimeleft += 20;
vehicleIncome += route.GetRouteValue() * route.GetTripTime();
runningCosts += triptimeleft * (AIVehicle.GetRunningCost(vehicleID)/DAYS_PER_YEAR);
vehicleMoney += AIVehicle.GetCurrentValue(vehicleID) - ((AIVehicle.GetCurrentValue(vehicleID) * 0.16) * (triptimeleft / DAYS_PER_YEAR));
//last thing we do is to subtract the stationmaintenance we overcalculated earlier due to ticks lost for ordering and selling vehicles.
local discountmonths = ((daysuntilend - triptimeleft) / 30.5).tointeger();
maintenancediscount += discountmonths * MONTHLY_STATION_MAINTENANCE * 2;
} else if (vehicle && vehicle.GetRoute() && vehicle.IsHinUndWieder()) {
local route = vehicle.GetRoute();
vehicleIncome += (route.GetRouteValue() * route.GetTripTime());
local hinundwiederfactor = 1;
local destination = AIOrder.ResolveOrderPosition(vehicleID, AIOrder.ORDER_CURRENT);
if (destination == 1) hinundwiederfactor = 0.5;
else hinundwiederfactor = 1.5;
local estimatedTripTimeLeft = route.GetTripTime() * hinundwiederfactor;//we may need a factor here...
runningCosts += (estimatedTripTimeLeft * AIVehicle.GetRunningCost(vehicleID))/DAYS_PER_YEAR;
vehicleMoney += AIVehicle.GetCurrentValue(vehicleID) - ((AIVehicle.GetCurrentValue(vehicleID) * 0.16) * (estimatedTripTimeLeft / DAYS_PER_YEAR));
//last thing we do is to subtract the stationmaintenance we overcalculated earlier due to ticks lost for ordering and selling vehicles.
local discountmonths = ((daysuntilend - estimatedTripTimeLeft) / 30.5).tointeger();
maintenancediscount += discountmonths * MONTHLY_STATION_MAINTENANCE * 2;
}
}
Debug("Running costs until end: " + runningCosts);
Debug("money stored in vehicles minus devaluation: " + vehicleMoney);
Debug("Income until end: " + vehicleIncome);
Debug("Discount on maintenance due to stations not built: " + maintenancediscount);
local totalBalance = vehicleIncome + GetAvailableMoney() + vehicleMoney;
costuntilend += runningCosts + stationMaintenance - maintenancediscount - stationsNotBuilt;
Debug("Total balance: " + totalBalance + "this has to be bigger than cost until end; " + costuntilend);
local diff = costuntilend - totalBalance;
Debug("The difference is: " + diff);
if(diff <= 0) {
Debug("Yup, it is time :)");
return 0; //no more datechange, thus start endgame.
} else {
Debug("Not time yet...");
if (diff < 250000)
return 1; //1 day until next check
if (diff < 500000)
return 2; //2 days until next check
if (diff < 750000)
return 3; //4 days until next check
if (diff < 1000000)
return 4; //10 days until next check
if (diff < 2000000)
return 5; //20 days until next check
if (diff < 3000000)
return 6; // 1 month until next check
if (diff < 5000000)
return 7; // 1.5 months until next check
return 8; // 2 months until next check
}
}
function TicksPerDay() {
//measure the number of ticks per day.
local dateOne = AIDate.GetCurrentDate();
while (dateOne == AIDate.GetCurrentDate()) {
Sleep(1);
}
dateOne = AIDate.GetCurrentDate();
local tickOne = AIController.GetTick();
while (dateOne == AIDate.GetCurrentDate()) {
Sleep(1);
}
local tickTwo = AIController.GetTick();
local ticksPerDay = tickTwo - tickOne;
return ticksPerDay;
Debug("Ticks per day: " + ticksPerDay);
}
function NameCompany() {
if (!AICompany.SetName(NAME)) {
local i = 2;
while (!AICompany.SetName(NAME + " #" + i)) i++;
}
}
function Save() {
// things to save:
// vehicles, stations, depots
// startEndgame, endgameCheck, endgameDate
// TODO
return {};
}
function Load(version, data) {
Debug("TODO: implement load and save");
}
}
function ManageVehicles() {
::INSTANCE.ManageVehicles();
}
rondje/route.nut 0000640 0063040 0023565 00000041072 11510620426 013264 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* Copyright 2008-2009 Marnix Bakker, Willem de Neve, Michiel Konstapel and Otto Visser.
* Suggestions/comments and bugs can go to: rondjeomdekerk@konstapel.nl
*/
require("util.nut");
const ALPHA = 0.3; // update rate of the exponential average
const JAM_DELAY = 1.2; // multiplier for vehicle age that determines whether a route is delayed/jammed
const BROKEN_DELAY = 3; // multiplier for vehicle age that determines whether a route might be broken
//const MINIMUM_SPEED = 34; // see http://wiki.openttd.org/index.php/Game_Mechanics#Vehicle_speeds
const MINIMUM_SPEED = 20; // 20 is slower than a vehicle would go on any terrain, including the slowest bridges
const INFINITE = 0; // "infinite" route distance
const SUBSIDY_MULTIPLIER = 2;
const JAM_CHECK_INTERVAL_DAYS = 7; // after a check, remember jammed status for this many days
/**
* Maintains persistent information about routes.
*/
class RouteDatabase {
routes = null;
constructor() {
routes = {};
}
/**
* Add route to the "database" if it is not already in.
* @return whether the route was added (new).
*/
function Add(route) {
local key = GetKey(route);
if (key in routes) return false;
Debug("Adding: " + key);
routes[key] <- RouteInfo(route);
return true;
}
function GetKey(route) {
return route.GetName();
}
function Update(route, tripTime, value) {
local routeInfo = routes[GetKey(route)];
if (routeInfo.isEstimate) {
// replace with real data
Debug("Replacing estimate for " + GetKey(route) + ": was " + routeInfo.value + ", is now: " + value + "G/d");
routeInfo.tripTime = tripTime;
routeInfo.value = value;
routeInfo.isEstimate = false;
} else {
// average with existing value
routeInfo.tripTime = (1-ALPHA)*routeInfo.tripTime + ALPHA*tripTime;
routeInfo.value = (1-ALPHA)*routeInfo.value + ALPHA*value;
//Debug("Route updated: " + GetKey(route) + ": " + routeInfo.value + " G/d, trip time " + routeInfo.tripTime + " days");
}
}
function SetValue(route, value) {
routes[GetKey(route)].value = value;
}
function GetValue(route) {
return routes[GetKey(route)].value;
}
function GetTripTime(route) {
return routes[GetKey(route)].tripTime;
}
function SetTripTime(route, tripTime) {
routes[GetKey(route)].tripTime = tripTime;
}
function IsBuildable(route) {
return routes[GetKey(route)].buildable;
}
function SetBuildable(route, buildable) {
routes[GetKey(route)].buildable = buildable;
}
function IsEstimate(route) {
return routes[GetKey(route)].isEstimate;
}
function GetDistance(route) {
return routes[GetKey(route)].distance;
}
function SetDistance(route, distance) {
routes[GetKey(route)].distance = distance;
}
function IsBuilt(route) {
return routes[GetKey(route)].built;
}
function SetBuilt(route) {
routes[GetKey(route)].built = true;
}
}
class RouteInfo {
value = 0;
tripTime = 0;
distance = 0;
buildable = true;
isEstimate = true;
built = false;
constructor(route) {
this.value = 0;
this.tripTime = 0;
this.distance = 0;
this.buildable = true;
this.isEstimate = true;
this.built = false;
}
}
class Route {
/**
* Maintains persistent info.
*/
static database = RouteDatabase();
from = null;
to = null;
network = null;
lastJamCheck = 0;
jammed = false;
broken = false;
name = null;
constructor(from, to, network) {
this.from = from;
this.to = to;
this.network = network;
this.lastJamCheck = 0;
this.jammed = false;
this.broken = false;
this.name = from.GetCargoLabel() + " from " + from.GetName() + " to " + to.GetName();
if (Route.database.Add(this)) {
Route.database.SetDistance(this, GetDrivingDistanceEstimate());
Route.database.SetValue(this, GetRouteValueEstimate());
Route.database.SetTripTime(this, GetTripTimeEstimate());
}
}
function _tostring() {
return GetName() + ": " +
GetDistance() + " tiles, " +
GetTripTime().tointeger() + " days, " +
GetRouteValue().tointeger() + " G/day, " +
(IsBuilt() ? GetNumberOfVehicles() + " vehicles" : "not built");
}
function GetName() {
return name;
}
/**
* Use the pathfinder to measure the actual distance and stores the result in the route database.
* @return the distance in tiles.
*/
function CalculateImprovedEstimate() {
local fromTile = FindDistanceEstimateRoadTile(from, to);
local toTile = FindDistanceEstimateRoadTile(to, from);
local pathfinder = ConnectedChecker(2*AIMap.DistanceManhattan(fromTile, toTile));
pathfinder.InitializePath([fromTile], [toTile]);
local distance;
try {
local tick = GetTick();
local path = false;
while (path == false) {
path = pathfinder.FindPath(VEHICLE_MANAGEMENT_INTERVAL);
ManageVehicles();
if (GetTick() - tick > MAX_PATHFINDING_TICKS) {
Warning("Pathfinding is taking too long!");
path = null;
break;
}
}
if (path == null) {
Warning("No path found!");
distance = INFINITE;
} else {
distance = path.GetCost() + 2; // add station tiles
Debug("Actual distance: " + distance + " tiles, estimate was " + GetDrivingDistanceEstimate());
}
} catch (e) {
Warning("Error during pathfinding!");
distance = INFINITE;
}
Route.database.SetDistance(this, distance);
Route.database.SetTripTime(this, GetTripTimeEstimate());
Route.database.SetValue(this, distance == INFINITE ? -1 : GetRouteValueEstimate());
}
/**
* Find the road tile at "from" to use for as a pathfinding endpoint.
*/
function FindDistanceEstimateRoadTile(from, to) {
// if we already have a station here *in the network*, use that as the endpoint
local fromStation = from.GetMyStation();
if (fromStation && network.Contains(fromStation.GetStationID()))
return fromStation.GetLocation();
local tiles = AITileList();
tiles.AddList(from.GetStationArea());
tiles.KeepList(network.tiles);
if (tiles.Count() == 0) {
// look further out
SafeAddRectangle(tiles, from.GetLocation(), 10);
tiles.KeepList(network.tiles);
if (tiles.Count() == 0) {
// still nothing
throw NoRoomForStationException(from);
}
}
return FindClosestTile(tiles, to.GetLocation());
}
function GetPickup() {
return from;
}
function GetDropoff() {
return to;
}
function GetPickupStation() {
return from.GetMyStation();
}
function GetDropoffStation() {
return to.GetMyStation();
}
/**
* Returns the estimated distance for this route.
*/
function GetDistance() {
return Route.database.GetDistance(this);
}
/**
* Returns true if this is not a passenger route.
*/
function IsFreight() {
return GetCargo() != PASSENGERS;
}
/**
* The type of cargo that this route provides.
*/
function GetCargo() {
return from.GetCargo();
}
/**
* The amount of cargo waiting at the source station.
*/
function GetCargoWaiting() {
return AIStation.GetCargoWaiting(from.GetMyStation().GetStationID(), from.GetCargo());
}
/**
* The cargo rating at the pickup station.
*/
function GetCargoRating() {
return AIStation.GetCargoRating(from.GetMyStation().GetStationID(), from.GetCargo());
}
/**
* Check whether there is an unawarded subsidy for this route.
*/
function IsSubsidized() {
local subsidies = AISubsidyList();
subsidies.Valuate(AISubsidy.IsAwarded);
subsidies.KeepValue(0);
subsidies.Valuate(AISubsidy.GetCargoType);
subsidies.KeepValue(GetCargo());
for (local subsidy = subsidies.Begin(); subsidies.HasNext(); subsidy = subsidies.Next()) {
// apparently this sometimes returns false even in all-passenger test games
// probably the "IsValid" or "IsAwarded" checks?
// local source = AISubsidy.SourceIsTown(subsidy) ? from.town.townID : from.industryID;
local source = IsFreight() ? from.industryID : from.town.townID;
local destination = IsFreight() ? to.industryID : to.town.townID;
if (AISubsidy.GetSourceIndex(subsidy) == source && AISubsidy.GetDestinationIndex(subsidy) == destination) {
return true;
}
}
return false;
}
/**
* True if both destinations exist.
*/
function IsValid() {
return from != null && to != null && from.Exists() && to.Exists();
}
/**
* True if the route has been built (stations, depots and connecting roads).
*/
function IsBuilt() {
return database.IsBuilt(this);
}
/**
* Mark the road as built.
*/
function SetBuilt() {
database.SetBuilt(this);
}
/**
* True if the route is built, the buildings are connected and the dropoff station accepts the route's cargo.
*/
function IsConnected() {
return IsBuilt() &&
Connected(from.GetMyDepot(), from.GetMyStation()) &&
Connected(from.GetMyStation(), to.GetMyStation()) &&
Connected(to.GetMyStation(), to.GetMyDepot()) &&
to.GetMyStation().AcceptsCargo(GetCargo());
}
/**
* A route is jammed if there are vehicles on it that are older than the expected trip time
* and that are moving too slow. It is broken if there are vehicles on it that are much older.
*/
function IsJammedOrBroken() {
if (AIDate.GetCurrentDate() - lastJamCheck < JAM_CHECK_INTERVAL_DAYS) {
return jammed || broken;
} else {
local maxJammedAge = (JAM_DELAY*GetTripTime()).tointeger();
local maxBrokenAge = (BROKEN_DELAY*GetTripTime()).tointeger();
local vehicles = GetVehicleList();
// only look at vehicles that haven't yet made their first run
vehicles.Valuate(GetVehicleProfit);
vehicles.KeepBelowValue(0);
// for jams, look for oldish vehicles that are moving too slowly
local jammedVehicles = AIList();
jammedVehicles.AddList(vehicles);
jammedVehicles.Valuate(AIVehicle.GetCurrentSpeed);
jammedVehicles.KeepAboveValue(0);
jammedVehicles.KeepBelowValue(MINIMUM_SPEED);
jammedVehicles.Valuate(AIVehicle.GetAge);
jammedVehicles.KeepAboveValue(maxJammedAge);
jammed = jammedVehicles.Count() > 0;
// for broken routes, look for vehicles that are very old
local brokenVehicles = AIList();
brokenVehicles.AddList(vehicles);
brokenVehicles.Valuate(AIVehicle.GetAge);
brokenVehicles.KeepAboveValue(maxBrokenAge);
broken = brokenVehicles.Count() > 0;
lastJamCheck = AIDate.GetCurrentDate();
if (jammed) Warning(GetName() + " is jammed");
if (broken) Warning(GetName() + " is broken");
return jammed || broken;
}
}
/**
* Returns the number of vehicles on this route.
*/
function GetNumberOfVehicles() {
return GetVehicleList().Count();
}
/**
* Return an AIVehicleList of vehicles on this route.
*/
function GetVehicleList() {
if (from.GetMyStation() == null || to.GetMyStation() == null) return AIList();
// count vehicles going from the pickup to dropoff station
local vehicles = AIVehicleList_Station(from.GetMyStation().stationID);
local dropoffLocation = to.GetMyStation().GetLocation();
vehicles.Valuate(AIOrder.GetOrderDestination, 1);
vehicles.KeepValue(dropoffLocation);
return vehicles;
}
/**
* Add a vehicle to this route by building one from the depot
* at the given destination.
*/
function AddVehicle() {
local depot = Depot.GetDepot(from);
local vehicles = GetVehicleList();
// don't clone hin und wieder vehicles, which don't have NO_LOAD orders at the dropoff
vehicles.Valuate(AIOrder.GetOrderFlags, 1);
vehicles.KeepValue(AIOrder.AIOF_NO_LOAD | AIOrder.AIOF_NON_STOP_INTERMEDIATE);
local prototype = vehicles.IsEmpty() ? null : vehicles.Begin();
local prototypeEngine = prototype ? AIVehicle.GetEngineType(prototype) : null;
local vehicleID;
if (vehicles.IsEmpty() || prototypeEngine != GetBestEngine(from.GetCargo())) {
// no suitable prototype, so build a vehicle from scratch
vehicleID = depot.BuildVehicle(from.GetCargo());
if (!AIVehicle.IsValidVehicle(vehicleID)) return null;
AIOrder.AppendOrder(vehicleID, from.GetMyStation().GetLocation(), AIOrder.AIOF_FULL_LOAD | AIOrder.AIOF_NON_STOP_INTERMEDIATE);
AIOrder.AppendOrder(vehicleID, to.GetMyStation().GetLocation(), AIOrder.AIOF_NO_LOAD | AIOrder.AIOF_NON_STOP_INTERMEDIATE);
AIOrder.AppendOrder(vehicleID, to.GetMyDepot().GetLocation(), AIOrder.AIOF_NON_STOP_INTERMEDIATE);
} else {
// clone the prototype to save 3 ticks on adding orders
vehicleID = depot.CloneVehicle(prototype);
if (!AIVehicle.IsValidVehicle(vehicleID)) return null;
}
AIVehicle.StartStopVehicle(vehicleID);
return Vehicle(vehicleID, this); // NB: constructor adds it to the id->vehicle table
}
/**
* Returns an estimate for the expected driving distance.
*/
function GetDrivingDistanceEstimate() {
// the actual path won't be a straight line from pickup to dropoff
return (1.5 * GetPaymentDistance()).tointeger();
}
/**
* Returns the Manhattan distance between the two destinations, or, if built, stations.
*/
function GetPaymentDistance() {
if(IsBuilt()) {
return AIMap.DistanceManhattan(from.GetMyStation().GetLocation(), to.GetMyStation().GetLocation());
} else {
local distance = AIMap.DistanceManhattan(from.GetLocation(), to.GetLocation());
// for passengers, assume the actual route will be shorter
// due to pickup/dropoff placement
if (!IsFreight()) distance -= DROPOFF_DISTANCE;
return distance;
}
}
/**
* Approximate time it'll take a vehicle to make one trip on this route, from pickup to dropoff.
*/
function GetTripTimeEstimate() {
local engine = GetBestEngine(from.GetCargo());
// convert listed speed in km/h to tiles per day
// vehicles won't drive at full speed the whole route (not even close),
// so estimate them at half their top speed
local tilesPerDay = (5.6/100) * AIEngine.GetMaxSpeed(engine)/2;
local loadingTime = 4; // 4 days to load or unload
// for passengers, add some city size dependent fudge to account for manoeuvring and traffic
local trafficDelay = IsFreight() ? 0 : from.town.GetRadius();
return loadingTime + trafficDelay + GetDistance()/tilesPerDay;
}
function GetTripTime() {
return Route.database.GetTripTime(this);
}
/**
* Income for a single haul, divided by the trip time, minus daily running costs.
*/
function GetRouteValueEstimate() {
local cargoID = from.GetCargo();
local engine = GetBestEngine(cargoID);
local tripTime = GetTripTimeEstimate();
local distance = GetPaymentDistance();
local unitIncome = AICargo.GetCargoIncome(cargoID, distance, tripTime.tointeger());
local units = AIEngine.GetCapacity(GetBestEngine(cargoID));
return (unitIncome * units / tripTime) - (AIEngine.GetRunningCost(engine)/DAYS_PER_YEAR);
}
function IsValueConfirmed() {
return !Route.database.IsEstimate(this);
}
function SetRouteValue(value) {
Route.database.SetValue(this, value);
}
function GetRouteValue() {
local value = Route.database.GetValue(this);
// take the subsidy multiplier into account for estimates
// (not for confirmed routes, because extra profit is reported by the vehicle)
if (!IsValueConfirmed() && IsSubsidized()) value *= SUBSIDY_MULTIPLIER;
return value;
}
function Update(tripTime, value) {
database.Update(this, tripTime, value);
}
function SetBuildable(buildable) {
database.SetBuildable(this, buildable);
}
function IsBuildable() {
return database.IsBuildable(this) && GetDistance() != INFINITE;
}
/**
* Compare routes by estimated profitability.
*/
static function CompareRouteIncome(a, b) {
if (a.GetRouteValue() > b.GetRouteValue()) return -1;
if (a.GetRouteValue() < b.GetRouteValue()) return 1;
if (a.from.GetProduction() > b.from.GetProduction()) return -1;
if (a.from.GetProduction() < b.from.GetProduction()) return 1;
return 0;
}
}
rondje/builder.nut 0000640 0063040 0023565 00000037434 11250235463 013567 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* Copyright 2008-2009 Marnix Bakker, Willem de Neve, Michiel Konstapel and Otto Visser.
* Suggestions/comments and bugs can go to: rondjeomdekerk@konstapel.nl
*/
require("RoadFinder/graph/AStar.nut");
require("RoadFinder/RoadFinder.nut");
require("RoadFinder/ConnectedChecker.nut");
const RETRIES = 10;
class BuildException {
msg = null;
constructor(msg) {
this.msg = msg;
}
function _tostring() {
return msg;
}
}
class PathfindingException extends BuildException {
constructor(from, to) {
BuildException.constructor("no path from " + from + " to " + to);
}
}
class NoRoomForStationException extends BuildException {
constructor(destination) {
Debug("no room for station at " + destination.GetName());
BuildException.constructor("no room for station at " + destination.GetName());
}
}
class NoRoomForDepotException extends BuildException {
constructor(destination) {
Debug("no room for depot at " + destination.GetName());
BuildException.constructor("no room for depot at " + destination.GetName());
}
}
class NotEnoughMoneyException extends BuildException {
constructor() {
BuildException.constructor("not enough money");
}
}
class PissedOffAuthorityException extends BuildException {
constructor(destination) {
BuildException.constructor("pissed off the local authority in " + destination.GetName());
}
}
class RoadBuildingException extends BuildException {
constructor(msg) {
BuildException.constructor("couldn't build road: " + msg);
}
}
/**
* Build a route between two Destinations that are already connected by a road network.
* @return [pickupStation, pickupDepot, dropoffStation, dropoffDepot]
* @throw when a complete route could not be built
*/
function BuildRoute(route) {
MaxLoan();
local network = route.network;
local pickup = route.from;
local dropoff = route.to;
local pickupStation = null;
local pickupDepot = null;
local dropoffStation = null;
local dropoffDepot = null;
Debug("Building pickup station at " + pickup.GetName());
pickupStation = BuildStation(pickup, dropoff, ListToArray(pickup.GetPickupArea()), network);
Debug("Building dropoff station at " + dropoff.GetName());
dropoffStation = BuildStation(dropoff, pickup, ListToArray(dropoff.GetDropoffArea()), network);
Debug("Building pickup depot at " + pickup.GetName());
pickupDepot = BuildDepot(pickup, pickupStation);
Debug("Building dropoff depot at " + pickup.GetName());
dropoffDepot = BuildDepot(dropoff, dropoffStation);
pickup.SetMyStation(pickupStation);
dropoff.SetMyStation(dropoffStation);
route.SetBuilt();
return [pickupStation, pickupDepot, dropoffStation, dropoffDepot];
}
/**
* Build a station.
* @param at Destination to build at
* @param to Destination to connect to
* @param network Network to connect to
* @param area Array of tiles to build in
*/
function BuildStation(at, to, area, network) {
if (area.len() == 0) {
throw NoRoomForStationException(at);
}
// find the tile in the network near "at" that is closest to "to"
// but not in "area", because we need a two-tile route at least to figure out
// our station front tile
local tiles = AITileList();
SafeAddRectangle(tiles, at.GetLocation(), 10);
tiles.KeepList(network.tiles);
tiles.RemoveList(ArrayToList(area));
if (tiles.Count() == 0) {
throw NoRoomForStationException(at);
}
local connectTo = FindClosestTile(tiles, to.GetLocation());
//Sign(connectTo, "connect " + at.GetName());
local result;
local station = at.GetMyStation();
if (station) {
// reuse the station, but ensure it is connected!
Debug("We already have a station at " + at.GetName());
local path = FindPath([station.GetLocation()], [connectTo]);
if (path == null)
throw PathfindingException(station.GetName(), "tile " + connectTo);
BuildRoad(path);
result = station;
} else {
// build a road and a new station
local path = FindPath([connectTo], area);
if (path == null) {
throw PathfindingException(at.GetName(), "tile " + connectTo);
}
BuildRoad(path);
result = Build(at, area, path, true, 0);
}
return result;
}
/**
* Find the tile in AITileList tiles that is closest to the target tile.
*/
function FindClosestTile(tiles, target) {
local closest = tiles.Begin();
for (local tile = tiles.Next(); tiles.HasNext(); tile = tiles.Next()) {
if (AIMap.DistanceManhattan(tile, target) < AIMap.DistanceManhattan(closest, target)) closest = tile;
}
return closest;
}
/**
* Build a depot.
* @param destination Destination to build at
* @param station Station to connect to
*/
function BuildDepot(destination, station) {
local depot = destination.GetMyDepot();
if (depot) return depot;
local stationTile = station.GetLocation();
// for passenger routes, we're building in the town, so try and clear a spot for a depot
//if (destination.GetCargo() == PASSENGERS) ClearForDepot(stationTile);
// find buildable tiles around the station
local area = AITileList();
SafeAddRectangle(area, stationTile, DEPOT_RANGE);
area.Valuate(AITile.IsBuildable);
area.KeepValue(1);
if (area.Count() == 0) { // no room: make room
ClearForDepot(stationTile);
area = AITileList();
SafeAddRectangle(area, stationTile, DEPOT_RANGE);
area.Valuate(AITile.IsBuildable);
area.KeepValue(1);
}
if (area.Count() == 0) // failed to make room
throw PathfindingException("depot at " + destination.GetName(), station.GetName());
local path = FindPath([stationTile], ListToArray(area));
if (path == null) { // try it the destructive way
ClearForDepot(stationTile);
path = FindPath([stationTile], ListToArray(area));
}
if (path == null) // still no luck
throw PathfindingException("destructive depot at " + destination.GetName(), station.GetName());
BuildRoad(path);
return Build(destination, ListToArray(area), path, false, 0);
}
function ClearForDepot(stationTile) {
local depotTiles = AITileList();
// try to clear the front and back tiles
depotTiles.AddTile(stationTile + AIMap.GetTileIndex( 1, 0));
depotTiles.AddTile(stationTile + AIMap.GetTileIndex(-1, 0));
depotTiles.AddTile(stationTile + AIMap.GetTileIndex( 0, 1));
depotTiles.AddTile(stationTile + AIMap.GetTileIndex( 0, -1));
RemoveDriveThroughSideTiles(depotTiles, stationTile);
for (local tile = depotTiles.Begin(); depotTiles.HasNext(); tile = depotTiles.Next()) {
// don't destroy road tiles
if (!AIRoad.IsRoadTile(tile)) {
// stop if we clear a spot
if (AITile.DemolishTile(tile)) break;
}
}
}
/**
* Remove the two tiles to the side of a drivethrough station
* from an AITileList.
*/
function RemoveDriveThroughSideTiles(tiles, stationTile) {
if (!AIRoad.IsDriveThroughRoadStationTile(stationTile)) return;
if (AIMap.GetTileX(stationTile) == AIMap.GetTileX(AIRoad.GetRoadStationFrontTile(stationTile))) {
// oriented along the X axis -> remove the X +- 1 tiles
tiles.RemoveTile(stationTile - AIMap.GetTileIndex(1, 0));
tiles.RemoveTile(stationTile - AIMap.GetTileIndex(-1, 0));
} else {
// oriented along the Y axis -> remove the Y +- 1 tiles
tiles.RemoveTile(stationTile - AIMap.GetTileIndex(0, 1));
tiles.RemoveTile(stationTile - AIMap.GetTileIndex(0, -1));
}
return tiles;
}
/**
* Build a station or depot.
* @param destination Destination to build at
* @param area array of tiles to build in
* @param path path to connect to
* @param start whether to connect to the start (true) or end (false) of the path
* @param station build a station (true) or depot (false);
* @param retries number of retries we had due to ERR_NONE errors
*/
function Build(destination, area, path, station, retries) {
local tiles = StartOfPath(path);
local tile = tiles[0];
local exit = tiles[1];
local building = null;
if (station) {
local type = destination.GetStationType() == AIStation.STATION_TRUCK_STOP ? AIRoad.ROADVEHTYPE_TRUCK : AIRoad.ROADVEHTYPE_BUS;
if (AIRoad.BuildDriveThroughRoadStation(tile, exit, type, AIStation.STATION_NEW)) {
// station names and signs are limited to 30 characters
local name = destination.GetName();
if (name.len() > 30) name = name.slice(0, 27) + "...";
local stationID = AIStation.GetStationID(tile);
AIStation.SetName(stationID, name);
return Station(stationID, tile, destination);
}
} else {
if (AIRoad.BuildRoadDepot(tile, exit)) {
Debug("Built depot at " + destination.GetName());
return Depot(tile, destination);
}
}
local error = AIError.GetLastError();
Debug(AIError.GetLastErrorString());
local removeTile = false;
switch (error) {
case AIError.ERR_VEHICLE_IN_THE_WAY:
// give it the option to get out of the way
case AIError.ERR_NONE:
PrintError();
// shouldn't happen, but it does
// just retrying seems to work
// however, we don't want to end up in an infinite loop due to some freak occurence
retries++;
if (retries == RETRIES) {
retries = 0;
removeTile = true;
}
break;
case AIError.ERR_NOT_ENOUGH_CASH:
// we'll retry later
throw NotEnoughMoneyException();
case AIError.ERR_LOCAL_AUTHORITY_REFUSES:
// we managed to get a very poor or worse town rating
// give them trees to hug and/or leave town alone for now
throw PissedOffAuthorityException(destination);
case AIError.ERR_AREA_NOT_CLEAR:
// if it is not a road, demolish and retry
// this also prevents destroying our other stations
if (!AIRoad.IsRoadTile(path.GetTile()) && AITile.DemolishTile(path.GetTile())) {
// try again in the same spot
} else {
// try elsewhere
removeTile = true;
}
break;
default:
removeTile = true;
break;
}
//Sign(tile, AIError.GetLastErrorString());
if (removeTile) {
Debug("Area size left: " + area.len());
// abandon this spot
area.remove(IndexOf(area, tile));
if (area.len() == 0)
throw (station ? NoRoomForStationException(destination) : NoRoomForDepotException(destination));
// connect to the previous tile
path = FindPath([tile], area);
if (path == null)
throw (station ? NoRoomForStationException(destination) : NoRoomForDepotException(destination));
BuildRoad(path);
}
return Build(destination, area, path, station, retries);
}
/**
* Return the two nodes at a start of a path (building and building exit).
*/
function StartOfPath(path) {
return [path.GetTile(), path.GetParent().GetTile()];
}
/**
* Return the two nodes at a end of a path (building and building exit).
*/
function EndOfPath(path) {
// traverse the path to find the other end
local p = path.GetParent();
while (p.GetParent().GetParent() != null) {
p = p.GetParent();
}
return [p.GetParent().GetTile(), p.GetTile()];
}
/**
* Verify that two MapObjects are in fact connected by roads.
*/
function Connected(a, b) {
local max_cost = 3*AIMap.DistanceManhattan(a.GetLocation(), b.GetLocation());
local pathfinder = ConnectedChecker(max_cost);
pathfinder.InitializePath([a.GetLocation()], [b.GetLocation()]);
local path = false;
while (path == false) {
path = pathfinder.FindPath(VEHICLE_MANAGEMENT_INTERVAL);
ManageVehicles();
}
return path != null;
}
/**
* Return a RoadPathFinder path, or null if no path was found.
*/
function FindPath(startTiles, endTiles) {
try {
//local pathfinder = RoadPathFinder();
local pathfinder = RoadFinder();
// since we connect to existing road networks manually,
// don't worry too much about prebuilt roads
pathfinder.cost.tile = 1;
pathfinder.cost.max_cost = 15*AIMap.DistanceManhattan(startTiles[0], endTiles[0]);
pathfinder.cost.no_existing_road = 3;
pathfinder.cost.turn = 1;
pathfinder.cost.slope = 1;
pathfinder.cost.coast = 20;
pathfinder.cost.bridge_per_tile = 100;
pathfinder.cost.tunnel_per_tile = 100;
pathfinder.InitializePath(startTiles, endTiles);
Debug("Pathfinding...");
local path = false;
local tick = GetTick();
while (path == false) {
path = pathfinder.FindPath(VEHICLE_MANAGEMENT_INTERVAL);
ManageVehicles();
if ((GetTick() - tick) > MAX_PATHFINDING_TICKS) {
Warning("Pathfinding took more than " + MAX_PATHFINDING_TICKS + " ticks, aborting");
path = null;
break;
}
}
return path;
} catch (e) {
AILog.Error("Path finder: " + e);
return null;
}
}
/**
* Build a road for a pathfinder path.
*/
function BuildRoad(path) {
Debug("Building road...");
while (path != null) {
local par = path.GetParent();
if (par != null) {
local count = 0;
while (!BuildSegment(path, par)) {
// see if it was an actual error
if (AIError.GetLastError() == AIError.ERR_ALREADY_BUILT) break;
PrintError();
count++;
// retry N times
if (count > RETRIES) {
throw RoadBuildingException(AIError.GetLastErrorString());
}
switch (AIError.GetLastError()) {
case AIError.ERR_NONE:
// shouldn't happen, but it does
// just retrying seems to work
//Sign(path, "E_N");
break;
case AIError.ERR_AREA_NOT_CLEAR:
// demolish and retry
AITile.DemolishTile(path.GetTile());
break;
case AIError.ERR_VEHICLE_IN_THE_WAY:
// wait and retry, backing off longer and longer with each retry
Sleep(count);
break;
default:
// all other errors mean we can't build this path
throw RoadBuildingException(AIError.GetLastErrorString());
}
}
count = 0;
}
path = par;
}
}
/**
* Build a segment of a path and return whether this was successful.
*/
function BuildSegment(path, par) {
if (AIMap.DistanceManhattan(path.GetTile(), par.GetTile()) == 1 ) {
// verify the connection after building to catch, for example,
// trying to build into the side of a drive-through station
return AIRoad.BuildRoad(path.GetTile(), par.GetTile()) && AIRoad.AreRoadTilesConnected(path.GetTile(), par.GetTile());
} else {
/* Build a bridge or tunnel. */
if (!AIBridge.IsBridgeTile(path.GetTile()) && !AITunnel.IsTunnelTile(path.GetTile())) {
/* If it was a road tile, demolish it first. Do this to work around expended roadbits. */
if (AIRoad.IsRoadTile(path.GetTile())) AITile.DemolishTile(path.GetTile());
if (AITunnel.GetOtherTunnelEnd(path.GetTile()) == par.GetTile()) {
return AITunnel.BuildTunnel(AIVehicle.VT_ROAD, path.GetTile());
} else {
local bridges = AIBridgeList_Length(AIMap.DistanceManhattan(path.GetTile(), par.GetTile()) + 1);
bridges.Valuate(AIBridge.GetMaxSpeed);
bridges.Sort(AIAbstractList.SORT_BY_VALUE, false);
return AIBridge.BuildBridge(AIVehicle.VT_ROAD, bridges.Begin(), path.GetTile(), par.GetTile());
}
}
}
}
function BuildHQ(area) {
Debug("Building company HQ...");
for (local tile = area.Begin(); area.HasNext(); tile = area.Next()) {
if (AICompany.BuildCompanyHQ(tile)) {
Sign(tile, NAME + " HQ");
return;
} else {
PrintError();
//Sign(tile, AIError.GetLastErrorString());
}
}
Debug("No possible HQ location found");
}
rondje/RoadFinder/graph/queue/BinHeap.nut 0000644 0063040 0023565 00000007137 11136321536 017712 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* This file is for the greater part based on the work of Truebrain
* and only differs in some speed optimizations.
*/
/**
* Binary Heap.
* Peek and Remove always return the current lowest value in the list.
* Sort is done on insertion and on deletion.
*/
class BinHeap
{
_queue = null;
//_count = 0;
constructor()
{
_queue = [];
}
/**
* Insert a new entry in the list.
* The complexity of this operation is O(ln n).
* @param item The item to add to the list.
* @param priority The priority this item has.
*/
function Insert(item, priority);
/**
* Pop the first entry of the list.
* This is always the item with the lowest priority.
* The complexity of this operation is O(ln n).
* @return The item of the entry with the lowest priority.
*/
function Pop();
/**
* Peek the first entry of the list.
* This is always the item with the lowest priority.
* The complexity of this operation is O(1).
* @return The item of the entry with the lowest priority.
*/
function Peek();
/**
* Get the amount of current items in the list.
* The complexity of this operation is O(1).
* @return The amount of items currently in the list.
*/
function Count();
/**
* Check if an item exists in the list.
* The complexity of this operation is O(n).
* @param item The item to check for.
* @return True if the item is already in the list.
*/
function Exists(item);
}
function BinHeap::Insert(item, priority)
{
/* Append dummy entry */
_queue.append(0);
//this._count++;
local hole;
/* Find the point of insertion */
for (hole = _queue.len() - 1; hole > 0 && priority <= this._queue[hole / 2][1]; hole /= 2)
_queue[hole] = _queue[hole / 2];
/* Insert new pair */
_queue[hole] = [item, priority];
return true;
}
function BinHeap::Pop()
{
if (_queue.len() == 0) return null;
local node = _queue[0];
/* Remove the item from the list by putting the last value on top */
_queue[0] = _queue[_queue.len() - 1];
_queue.pop();
//_count--;
/* Bubble down the last value to correct the tree again */
_BubbleDown();
return node[0];
}
function BinHeap::Peek()
{
if (_queue.len() == 0) return null;
return _queue[0][0];
}
function BinHeap::Count()
{
return _queue.len();
}
function BinHeap::Exists(item)
{
/* Brute-force find the item (there is no faster way, as we don't have the priority number) */
foreach (node in _queue) {
if (node[0] == item) return true;
}
return false;
}
function BinHeap::_BubbleDown()
{
if (_queue.len() == 0) return;
local hole = 1;
local tmp = _queue[0];
/* Start switching parent and child until the tree is restored */
while (hole * 2 < _queue.len() + 1) {
local child = hole * 2;
if (child != _queue.len() && _queue[child][1] <= _queue[child - 1][1]) child++;
if (_queue[child - 1][1] > tmp[1]) break;
_queue[hole - 1] = _queue[child - 1], hole = child;
}
/* The top value is now at his new place */
_queue[hole - 1] = tmp;
}
rondje/RoadFinder/graph/AStar.nut 0000644 0063040 0023565 00000020213 11136321576 016264 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* This file is for the greater part based on the work of Truebrain
* and only differs in some speed optimizations.
*/
require("queue/BinHeap.nut");
/**
* An A* implementation.
* It solves graphs by finding the fastest route from one point to the other.
*/
class AStar {
_queue_class = BinHeap;
_cost_callback = null;
_estimate_callback = null;
_neighbours_callback = null;
_cost_callback_param = null;
_estimate_callback_param = null;
_neighbours_callback_param = null;
_open = null;
_closed = null;
_goals = null;
/**
* @param cost_callback A function that returns the cost of a path. It
* should accept four parameters, old_path, new_tile, new_direction and
* cost_callback_param. old_path is an instance of AStar.Path, and
* new_node is the new node that is added to that path. It should return
* the cost of the path including new_node.
* @param estimate_callback A function that returns an estimate from a node
* to the goal node. It should accept four parameters, tile, direction,
* goal_nodes and estimate_callback_param. It should return an estimate to
* the cost from the lowest cost between node and any node out of goal_nodes.
* Note that this estimate is not allowed to be higher than the real cost
* between node and any of goal_nodes. A lower value is fine, however the
* closer it is to the real value, the better the performance.
* @param neighbours_callback A function that returns all neighbouring nodes
* from a given node. It should accept three parameters, current_path, node
* and neighbours_callback_param. It should return an array containing all
* neighbouring nodes, which are an array in the form [tile, direction].
* @param cost_callback_param This parameters will be passed to cost_callback
* as fourth parameter. Useful to send is an instance of an object.
* @param estimate_callback_param This parameters will be passed to
* estimate_callback as fourth parameter. Useful to send is an instance of an
* object.
* @param neighbours_callback_param This parameters will be passed to
* neighbours_callback as third parameter. Useful to send is an instance of
* an object.*/
constructor(cost_callback, estimate_callback, neighbours_callback, cost_callback_param = null, estimate_callback_param = null, neighbours_callback_param = null)
{
if (typeof(cost_callback) != "function") throw("'cost_callback' has to be a function-pointer.");
if (typeof(estimate_callback) != "function") throw("'estimate_callback' has to be a function-pointer.");
if (typeof(neighbours_callback) != "function") throw("'neighbours_callback' has to be a function-pointer.");
this._cost_callback = cost_callback;
this._estimate_callback = estimate_callback;
this._neighbours_callback = neighbours_callback;
this._cost_callback_param = cost_callback_param;
this._estimate_callback_param = estimate_callback_param;
this._neighbours_callback_param = neighbours_callback_param;
}
/**
* Initialize a path search between sources and goals.
* @param sources The source nodes, pairs of [tile, direction].
* @param goals The target tiles.
*/
function InitializePath(sources, goals);
/**
* Try to find the path as indicated with InitializePath with the lowest cost.
* @param iterations After how many iterations it should abort for a moment.
* This value should either be -1 for infinite, or > 0. Any other value
* aborts immediatly and will never find a path.
* @return A route if one was found, or false if the amount of iterations was
* reached, or null if no path was found.
* You can call this function over and over as long as it returns false,
* which is an indication it is not yet done looking for a route.
*/
function FindPath(iterations);
}
function AStar::InitializePath(sources, goals)
{
if (typeof(sources) != "array" || sources.len() == 0) throw("sources has be a non-empty array.");
if (typeof(goals) != "array" || goals.len() == 0) throw("goals has be a non-empty array.");
this._open = this._queue_class();
this._closed = AIList();
foreach (node in sources) {
if (node[1] <= 0) throw("directional value should never be zero or negative.");
local new_path = this.Path(null, node[0], node[1], this._cost_callback, this._cost_callback_param);
this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node[0], node[1], goals, this._estimate_callback_param));
}
this._goals = goals;
}
function AStar::FindPath(iterations)
{
if (this._open == null) throw("can't execute over an uninitialized path");
while (this._open.Count() && (iterations-- != 0)) {
/* Get the path with the best score so far */
local path = this._open.Pop();
local cur_tile = path.GetTile();
/* Make sure we didn't already passed it */
if (this._closed.HasItem(cur_tile)) {
/* If the direction is already on the list, skip this entry */
if ((this._closed.GetValue(cur_tile) & path.GetDirection()) != 0) continue;
/* Scan the path for a possible collision */
local scan_path = path.GetParent();
local mismatch = false;
while (scan_path != null) {
if (scan_path.GetTile() == cur_tile) {
mismatch = true;
break;
}
scan_path = scan_path.GetParent();
}
if (mismatch) continue;
/* Add the new direction */
this._closed.SetValue(cur_tile, this._closed.GetValue(cur_tile) | path.GetDirection());
} else {
/* New entry, make sure we don't check it again */
this._closed.AddItem(cur_tile, path.GetDirection());
}
/* Check if we found the end */
foreach (tile in this._goals) {
if (cur_tile == tile) {
this._CleanPath();
return path;
}
}
/* Scan all neighbours */
local neighbours = this._neighbours_callback(path, cur_tile, this._neighbours_callback_param);
foreach (node in neighbours) {
if (node[1] <= 0) throw("directional value should never be zero or negative.");
if ((this._closed.GetValue(node[0]) & node[1]) != 0) continue;
/* Calculate the new paths and add them to the open list */
local new_path = this.Path(path, node[0], node[1], this._cost_callback, this._cost_callback_param);
this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node[0], node[1], this._goals, this._estimate_callback_param));
}
}
if (this._open.Count() > 0) return false;
this._CleanPath();
return null;
}
function AStar::reset() {
this._CleanPath();
}
function AStar::_CleanPath()
{
this._closed = null;
this._open = null;
this._goals = null;
}
/**
* The path of the AStar algorithm.
* It is reversed, that is, the first entry is more close to the goal-nodes
* than his GetParent(). You can walk this list to find the whole path.
* The last entry has a GetParent() of null.
*/
class AStar.Path
{
_prev = null;
_tile = null;
_direction = null;
_cost = null;
constructor(old_path, new_tile, new_direction, cost_callback, cost_callback_param)
{
this._prev = old_path;
this._tile = new_tile;
this._direction = new_direction;
this._cost = cost_callback(old_path, new_tile, new_direction, cost_callback_param);
};
/**
* Return the tile where this (partial-)path ends.
*/
function GetTile() { return this._tile; }
/**
* Return the direction from which we entered the tile in this (partial-)path.
*/
function GetDirection() { return this._direction; }
/**
* Return an instance of this class leading to the previous node.
*/
function GetParent() { return this._prev; }
/**
* Return the cost of this (partial-)path from the beginning up to this node.
*/
function GetCost() { return this._cost; }
}
rondje/RoadFinder/RoadFinder.nut 0000644 0063040 0023565 00000032035 11136322127 016164 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* This file is for the greater part based on the work of Truebrain
* but has been heavily optimized for speed but also takes into account
* the cost of farmland etc.
*/
require("graph/AStar.nut");
/**
* A Road Pathfinder.
* This road pathfinder tries to find a buildable / existing route for
* road vehicles. You can changes the costs below using for example
* roadpf.cost.turn = 30. Note that it's not allowed to change the cost
* between consecutive calls to FindPath. You can change the cost before
* the first call to FindPath and after FindPath has returned an actual
* route. To use only existing roads, set cost.no_existing_road to
* cost.max_cost.
*/
class RoadFinder
{
_max_cost = null; ///< The maximum cost for a route.
_cost_tile = null; ///< The cost for a single tile.
_cost_no_existing_road = null; ///< The cost that is added to _cost_tile if no road exists yet.
_cost_turn = null; ///< The cost that is added to _cost_tile if the direction changes.
_cost_slope = null; ///< The extra cost if a road tile is sloped.
_cost_bridge_per_tile = null; ///< The cost per tile of a new bridge, this is added to _cost_tile.
_cost_tunnel_per_tile = null; ///< The cost per tile of a new tunnel, this is added to _cost_tile.
_cost_coast = null; ///< The extra cost for a coast tile.
_pathfinder = null; ///< A reference to the used AyStar object.
_max_bridge_length = null; ///< The maximum length of a bridge that will be build.
_max_tunnel_length = null; ///< The maximum length of a tunnel that will be build.
cost = null; ///< Used to change the costs.
_running = null;
constructor()
{
this._max_cost = 100000;
this._cost_tile = 30;
this._cost_no_existing_road = 130;
this._cost_turn = 100;
this._cost_slope = 200;
this._cost_bridge_per_tile = 150;
this._cost_tunnel_per_tile = 120;
this._cost_coast = 20;
this._max_bridge_length = 10;
this._max_tunnel_length = 20;
this._pathfinder = AStar(this._Cost, this._Estimate, this._Neighbours, this, this, this);
this.cost = this.Cost(this);
this._running = false;
}
/**
* Initialize a path search between sources and goals.
* @param sources The source tiles.
* @param goals The target tiles.
* @see AyStar::InitializePath()
*/
function InitializePath(sources, goals) {
local nsources = [];
foreach (node in sources) {
nsources.push([node, 0xFF]);
}
this._pathfinder.InitializePath(nsources, goals);
}
}
class RoadFinder.Cost
{
_main = null;
function _set(idx, val)
{
if (this._main._running) throw("You are not allowed to change parameters of a running pathfinder.");
switch (idx) {
case "max_cost": this._main._max_cost = val; break;
case "tile": this._main._cost_tile = val; break;
case "no_existing_road": this._main._cost_no_existing_road = val; break;
case "turn": this._main._cost_turn = val; break;
case "slope": this._main._cost_slope = val; break;
case "bridge_per_tile": this._main._cost_bridge_per_tile = val; break;
case "tunnel_per_tile": this._main._cost_tunnel_per_tile = val; break;
case "coast": this._main._cost_coast = val; break;
case "max_bridge_length": this._main._max_bridge_length = val; break;
case "max_tunnel_length": this._main._max_tunnel_length = val; break;
default: throw("the index '" + idx + "' does not exist");
}
return val;
}
function _get(idx)
{
switch (idx) {
case "max_cost": return this._main._max_cost;
case "tile": return this._main._cost_tile;
case "no_existing_road": return this._main._cost_no_existing_road;
case "turn": return this._main._cost_turn;
case "slope": return this._main._cost_slope;
case "bridge_per_tile": return this._main._cost_bridge_per_tile;
case "tunnel_per_tile": return this._main._cost_tunnel_per_tile;
case "coast": return this._main._cost_coast;
case "max_bridge_length": return this._main._max_bridge_length;
case "max_tunnel_length": return this._main._max_tunnel_length;
default: throw("the index '" + idx + "' does not exist");
}
}
function constructor(main)
{
this._main = main;
}
}
/**
* Try to find the path as indicated with InitializePath with the lowest cost.
* @param iterations After how many iterations it should abort for a moment.
* This value should either be -1 for infinite, or > 0. Any other value
* aborts immediatly and will never find a path.
* @return A route if one was found, or false if the amount of iterations was
* reached, or null if no path was found.
* You can call this function over and over as long as it returns false,
* which is an indication it is not yet done looking for a route.
* @see AyStar::FindPath()
*/
function RoadFinder::FindPath(iterations)
{
local test_mode = AITestMode();
local ret = this._pathfinder.FindPath(iterations);
this._running = (ret == false) ? true : false;
return ret;
}
function RoadFinder::reset() {
this._pathfinder.reset();
this._running = false;
}
function RoadFinder::_Cost(path, new_tile, new_direction, self) {
/* path == null means this is the first node of a path, so the cost is 0. */
if (path == null) return 0;
local prev_tile = path.GetTile();
if (AIRoad.AreRoadTilesConnected(prev_tile, new_tile)) {
return path.GetCost() + self._cost_tile;
}
/* If the two tiles are more then 1 tile apart, the pathfinder wants a bridge or tunnel
* to be build. It isn't an existing bridge / tunnel, as that case is already handled. */
if (AIMap.DistanceManhattan(new_tile, prev_tile) > 1) {
/* Check if we should build a bridge or a tunnel. */
if (AITunnel.GetOtherTunnelEnd(new_tile) == prev_tile) {
return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_tunnel_per_tile);
} else {
return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_bridge_per_tile) + 2 * self._cost_slope;
}
}
local cost = self._cost_no_existing_road
/* Check if the new tile is a coast tile or a farm tile (404 and 540 actual extra cost). */
if (AITile.IsCoastTile(new_tile) || AITile.IsFarmTile(new_tile)) {
cost += self._cost_coast;
}
/* Check if the last tile was sloped or rock tile (actual costs: 281 and 203). */
if (AITile.GetSlope(new_tile) != AITile.SLOPE_FLAT || AITile.IsRockTile(new_tile)) {
cost += self._cost_slope;
}
/* Check for a turn. We do this by substracting the TileID of the current node from
* the TileID of the previous node and comparing that to the difference between the
* previous node and the node before that. */
if (path.GetParent() != null && (prev_tile - path.GetParent().GetTile()) != (new_tile - prev_tile)) {
return path.GetCost() + cost + self._cost_turn;
}
return path.GetCost() + cost;
}
function RoadFinder::_Estimate(cur_tile, cur_direction, goal_tiles, self) {
local min_cost = self._max_cost;
/* As estimate we multiply the cost for a single new road tile with
* with the minimum number of tiles we need to traverse. */
foreach (tile in goal_tiles) {
min_cost = min(AIMap.DistanceManhattan(cur_tile, tile) * self._cost_no_existing_road, min_cost);
}
return min_cost;
}
function RoadFinder::_Neighbours(path, cur_node, self)
{
/* self._max_cost is the maximum path cost, if we go over it, the path isn't valid. */
if (path.GetCost() >= self._max_cost) return [];
local tiles = [];
/* Check if the current tile is part of a bridge or tunnel. */
if ((AIBridge.IsBridgeTile(cur_node) || AITunnel.IsTunnelTile(cur_node)) &&
AITile.HasTransportType(cur_node, AITile.TRANSPORT_ROAD)) {
local other_end = AIBridge.IsBridgeTile(cur_node) ? AIBridge.GetOtherBridgeEnd(cur_node) : AITunnel.GetOtherTunnelEnd(cur_node);
local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AITile.IsBuildable(next_tile) || AIRoad.IsRoadTile(next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
}
/* The other end of the bridge / tunnel is a neighbour. */
tiles.push([other_end, self._GetDirection(next_tile, cur_node, true) << 4]);
} else if (path.GetParent() != null && AIMap.DistanceManhattan(cur_node, path.GetParent().GetTile()) > 1) {
local other_end = path.GetParent().GetTile();
local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AIRoad.BuildRoad(cur_node, next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
}
} else {
local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
/* Check all tiles adjacent to the current tile. */
foreach (offset in offsets) {
local next_tile = cur_node + offset;
/* We add them to the to the neighbours-list if one of the following applies:
* 1) There already is a connections between the current tile and the next tile.
* 2) We can build a road to the next tile.
* 3) The next tile is the entrance of a tunnel / bridge in the correct direction. */
if (AIRoad.AreRoadTilesConnected(cur_node, next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
} else if ((AITile.IsBuildable(next_tile) || AIRoad.IsRoadTile(next_tile)) &&
(path.GetParent() == null || AIRoad.CanBuildConnectedRoadPartsHere(cur_node, path.GetParent().GetTile(), next_tile)) &&
AIRoad.BuildRoad(cur_node, next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
} else if (self._CheckTunnelBridge(cur_node, next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
}
}
if (path.GetParent() != null) {
local bridges = self._GetTunnelsBridges(path.GetParent().GetTile(), cur_node, self._GetDirection(path.GetParent().GetTile(), cur_node, true) << 4);
foreach (tile in bridges) {
tiles.push(tile);
}
}
}
return tiles;
}
function RoadFinder::_GetDirection(from, to, is_bridge)
{
if (!is_bridge && AITile.GetSlope(to) == AITile.SLOPE_FLAT) return 0xFF;
if (from - to == 1) return 1;
if (from - to == -1) return 2;
if (from - to == AIMap.GetMapSizeX()) return 4;
if (from - to == -AIMap.GetMapSizeX()) return 8;
}
/**
* Get a list of all bridges and tunnels that can be build from the
* current tile. Bridges will only be build starting on non-flat tiles
* for performance reasons. Tunnels will only be build if no terraforming
* is needed on both ends.
*/
function RoadFinder::_GetTunnelsBridges(last_node, cur_node, bridge_dir)
{
local slope = AITile.GetSlope(cur_node);
if (slope == AITile.SLOPE_FLAT) return [];
local tiles = [];
for (local i = 2; i < this._max_bridge_length; i++) {
local bridge_list = AIBridgeList_Length(i + 1);
local target = cur_node + i * (cur_node - last_node);
if (!bridge_list.IsEmpty() && AIBridge.BuildBridge(AIVehicle.VT_ROAD, bridge_list.Begin(), cur_node, target)) {
tiles.push([target, bridge_dir]);
}
}
if (slope != AITile.SLOPE_SW && slope != AITile.SLOPE_NW && slope != AITile.SLOPE_SE && slope != AITile.SLOPE_NE) return tiles;
local other_tunnel_end = AITunnel.GetOtherTunnelEnd(cur_node);
if (!AIMap.IsValidTile(other_tunnel_end)) return tiles;
local tunnel_length = AIMap.DistanceManhattan(cur_node, other_tunnel_end);
local prev_tile = cur_node + (cur_node - other_tunnel_end) / tunnel_length;
if (AITunnel.GetOtherTunnelEnd(other_tunnel_end) == cur_node && tunnel_length >= 2 &&
prev_tile == last_node && tunnel_length < _max_tunnel_length && AITunnel.BuildTunnel(AIVehicle.VT_ROAD, cur_node)) {
tiles.push([other_tunnel_end, bridge_dir]);
}
return tiles;
}
function RoadFinder::_CheckTunnelBridge(current_tile, new_tile)
{
if (!AIBridge.IsBridgeTile(new_tile) && !AITunnel.IsTunnelTile(new_tile)) return false;
local dir = new_tile - current_tile;
local other_end = AIBridge.IsBridgeTile(new_tile) ? AIBridge.GetOtherBridgeEnd(new_tile) : AITunnel.GetOtherTunnelEnd(new_tile);
local dir2 = other_end - new_tile;
if ((dir < 0 && dir2 > 0) || (dir > 0 && dir2 < 0)) return false;
dir = abs(dir);
dir2 = abs(dir2);
if ((dir >= AIMap.GetMapSizeX() && dir2 < AIMap.GetMapSizeX()) ||
(dir < AIMap.GetMapSizeX() && dir2 >= AIMap.GetMapSizeX())) return false;
return true;
}
rondje/RoadFinder/ConnectedChecker.nut 0000644 0063040 0023565 00000014441 11136321553 017341 0 ustar visser staf /**
* This file is part of Rondje.
*
* Rondje is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Rondje is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Rondje. If not, see .
*
* This file is based on the RoadFinder class (which in turn is based on
* Truebrains work), but is a slimmed down version optimized for one goal:
* check whether two tiles are connected. This pathfinder can be run from
* the constructor as it does no do-commands at all.
*/
require("graph/AStar.nut");
/**
* A Road Pathfinder that is optimized for connectedness checking
*/
class ConnectedChecker {
_pathfinder = null; ///< A reference to the used AyStar object.
_running = null;
_max_cost = null;
constructor(max_cost) {
this._pathfinder = AStar(this._Cost, this._Estimate, this._Neighbours, this, this, this);
this._running = false;
this._max_cost = max_cost;
}
/**
* Initialize a path search between sources and goals.
* @param sources The source tiles.
* @param goals The target tiles.
* @see AyStar::InitializePath()
*/
function InitializePath(sources, goals) {
local nsources = [];
foreach (node in sources) {
nsources.push([node, 0xFF]);
}
this._pathfinder.InitializePath(nsources, goals);
}
/**
* Try to find the path as indicated with InitializePath with the lowest cost.
* @param iterations After how many iterations it should abort for a moment.
* This value should either be -1 for infinite, or > 0. Any other value
* aborts immediatly and will never find a path.
* @return A route if one was found, or false if the amount of iterations was
* reached, or null if no path was found.
* You can call this function over and over as long as it returns false,
* which is an indication it is not yet done looking for a route.
* @see AStar::FindPath()
*/
function FindPath(iterations) {
local ret = this._pathfinder.FindPath(iterations);
this._running = (ret == false) ? true : false;
return ret;
}
function reset() {
this._pathfinder.reset();
this._running = false;
}
function _Cost(path, new_tile, new_direction, self) {
/* path == null means this is the first node of a path, so the cost is 0. */
if (path == null)
return 0;
local prev_tile = path.GetTile();
if (AIRoad.AreRoadTilesConnected(prev_tile, new_tile)) {
return path.GetCost() + 1;
}
return self._max_cost;
}
function _Estimate(cur_tile, cur_direction, goal_tiles, self) {
local min_cost = self._max_cost;
/* As estimate we multiply the cost for a single new road tile with
* with the minimum number of tiles we need to traverse. */
foreach (tile in goal_tiles) {
min_cost = min(AIMap.DistanceManhattan(cur_tile, tile), min_cost);
}
return min_cost;
}
function _Neighbours(path, cur_node, self) {
/* If we go over max_cost, the path isn't valid. */
if (path.GetCost() >= self._max_cost)
return [];
local tiles = [];
/* Check if the current tile is part of a bridge or tunnel. */
if ((AIBridge.IsBridgeTile(cur_node) || AITunnel.IsTunnelTile(cur_node)) && AITile.HasTransportType(cur_node, AITile.TRANSPORT_ROAD)) {
local other_end = AIBridge.IsBridgeTile(cur_node) ? AIBridge.GetOtherBridgeEnd(cur_node) : AITunnel.GetOtherTunnelEnd(cur_node);
local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AIRoad.IsRoadTile(next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
}
/* The other end of the bridge / tunnel is a neighbour. */
tiles.push([other_end, self._GetDirection(next_tile, cur_node, true) << 4]);
} else if (path.GetParent() != null && AIMap.DistanceManhattan(cur_node, path.GetParent().GetTile()) > 1) {
local other_end = path.GetParent().GetTile();
local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
if (AIRoad.AreRoadTilesConnected(cur_node, next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
}
} else {
local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1), AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
/* Check all tiles adjacent to the current tile. */
foreach (offset in offsets) {
local next_tile = cur_node + offset;
/* We add them to the to the neighbours-list if one of the following applies:
* 1) There already is a connections between the current tile and the next tile.
* 2) We can build a road to the next tile.
* 3) The next tile is the entrance of a tunnel / bridge in the correct direction. */
if (AIRoad.AreRoadTilesConnected(cur_node, next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
} else if (self._CheckTunnelBridge(cur_node, next_tile)) {
tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
}
}
}
return tiles;
}
function _GetDirection(from, to, is_bridge) {
if (!is_bridge && AITile.GetSlope(to) == AITile.SLOPE_FLAT) return 0xFF;
if (from - to == 1) return 1;
if (from - to == -1) return 2;
if (from - to == AIMap.GetMapSizeX()) return 4;
if (from - to == -AIMap.GetMapSizeX()) return 8;
}
function _CheckTunnelBridge(current_tile, new_tile)
{
if (!AIBridge.IsBridgeTile(new_tile) && !AITunnel.IsTunnelTile(new_tile)) return false;
local dir = new_tile - current_tile;
local other_end = AIBridge.IsBridgeTile(new_tile) ? AIBridge.GetOtherBridgeEnd(new_tile) : AITunnel.GetOtherTunnelEnd(new_tile);
local dir2 = other_end - new_tile;
if ((dir < 0 && dir2 > 0) || (dir > 0 && dir2 < 0)) return false;
dir = abs(dir);
dir2 = abs(dir2);
if ((dir >= AIMap.GetMapSizeX() && dir2 < AIMap.GetMapSizeX()) ||
(dir < AIMap.GetMapSizeX() && dir2 >= AIMap.GetMapSizeX())) return false;
return true;
}
}
rondje/README 0000644 0063040 0023565 00000000315 11066670652 012271 0 ustar visser staf
All our code is released under GPL v2, we already made our profit by winning the TJIP challenge ;-)
Comments and suggestions are always welcome, please send them to: rondjeomdekerk@konstapel.nl
rondje/COPYING 0000644 0063040 0023565 00000043103 11066657303 012444 0 ustar visser staf GNU GENERAL PUBLIC LICENSE
Version 2, June 1991
Copyright (C) 1989, 1991 Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
Everyone is permitted to copy and distribute verbatim copies
of this license document, but changing it is not allowed.
Preamble
The licenses for most software are designed to take away your
freedom to share and change it. By contrast, the GNU General Public
License is intended to guarantee your freedom to share and change free
software--to make sure the software is free for all its users. This
General Public License applies to most of the Free Software
Foundation's software and to any other program whose authors commit to
using it. (Some other Free Software Foundation software is covered by
the GNU Lesser General Public License instead.) You can apply it to
your programs, too.
When we speak of free software, we are referring to freedom, not
price. Our General Public Licenses are designed to make sure that you
have the freedom to distribute copies of free software (and charge for
this service if you wish), that you receive source code or can get it
if you want it, that you can change the software or use pieces of it
in new free programs; and that you know you can do these things.
To protect your rights, we need to make restrictions that forbid
anyone to deny you these rights or to ask you to surrender the rights.
These restrictions translate to certain responsibilities for you if you
distribute copies of the software, or if you modify it.
For example, if you distribute copies of such a program, whether
gratis or for a fee, you must give the recipients all the rights that
you have. You must make sure that they, too, receive or can get the
source code. And you must show them these terms so they know their
rights.
We protect your rights with two steps: (1) copyright the software, and
(2) offer you this license which gives you legal permission to copy,
distribute and/or modify the software.
Also, for each author's protection and ours, we want to make certain
that everyone understands that there is no warranty for this free
software. If the software is modified by someone else and passed on, we
want its recipients to know that what they have is not the original, so
that any problems introduced by others will not reflect on the original
authors' reputations.
Finally, any free program is threatened constantly by software
patents. We wish to avoid the danger that redistributors of a free
program will individually obtain patent licenses, in effect making the
program proprietary. To prevent this, we have made it clear that any
patent must be licensed for everyone's free use or not licensed at all.
The precise terms and conditions for copying, distribution and
modification follow.
GNU GENERAL PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. This License applies to any program or other work which contains
a notice placed by the copyright holder saying it may be distributed
under the terms of this General Public License. The "Program", below,
refers to any such program or work, and a "work based on the Program"
means either the Program or any derivative work under copyright law:
that is to say, a work containing the Program or a portion of it,
either verbatim or with modifications and/or translated into another
language. (Hereinafter, translation is included without limitation in
the term "modification".) Each licensee is addressed as "you".
Activities other than copying, distribution and modification are not
covered by this License; they are outside its scope. The act of
running the Program is not restricted, and the output from the Program
is covered only if its contents constitute a work based on the
Program (independent of having been made by running the Program).
Whether that is true depends on what the Program does.
1. You may copy and distribute verbatim copies of the Program's
source code as you receive it, in any medium, provided that you
conspicuously and appropriately publish on each copy an appropriate
copyright notice and disclaimer of warranty; keep intact all the
notices that refer to this License and to the absence of any warranty;
and give any other recipients of the Program a copy of this License
along with the Program.
You may charge a fee for the physical act of transferring a copy, and
you may at your option offer warranty protection in exchange for a fee.
2. You may modify your copy or copies of the Program or any portion
of it, thus forming a work based on the Program, and copy and
distribute such modifications or work under the terms of Section 1
above, provided that you also meet all of these conditions:
a) You must cause the modified files to carry prominent notices
stating that you changed the files and the date of any change.
b) You must cause any work that you distribute or publish, that in
whole or in part contains or is derived from the Program or any
part thereof, to be licensed as a whole at no charge to all third
parties under the terms of this License.
c) If the modified program normally reads commands interactively
when run, you must cause it, when started running for such
interactive use in the most ordinary way, to print or display an
announcement including an appropriate copyright notice and a
notice that there is no warranty (or else, saying that you provide
a warranty) and that users may redistribute the program under
these conditions, and telling the user how to view a copy of this
License. (Exception: if the Program itself is interactive but
does not normally print such an announcement, your work based on
the Program is not required to print an announcement.)
These requirements apply to the modified work as a whole. If
identifiable sections of that work are not derived from the Program,
and can be reasonably considered independent and separate works in
themselves, then this License, and its terms, do not apply to those
sections when you distribute them as separate works. But when you
distribute the same sections as part of a whole which is a work based
on the Program, the distribution of the whole must be on the terms of
this License, whose permissions for other licensees extend to the
entire whole, and thus to each and every part regardless of who wrote it.
Thus, it is not the intent of this section to claim rights or contest
your rights to work written entirely by you; rather, the intent is to
exercise the right to control the distribution of derivative or
collective works based on the Program.
In addition, mere aggregation of another work not based on the Program
with the Program (or with a work based on the Program) on a volume of
a storage or distribution medium does not bring the other work under
the scope of this License.
3. You may copy and distribute the Program (or a work based on it,
under Section 2) in object code or executable form under the terms of
Sections 1 and 2 above provided that you also do one of the following:
a) Accompany it with the complete corresponding machine-readable
source code, which must be distributed under the terms of Sections
1 and 2 above on a medium customarily used for software interchange; or,
b) Accompany it with a written offer, valid for at least three
years, to give any third party, for a charge no more than your
cost of physically performing source distribution, a complete
machine-readable copy of the corresponding source code, to be
distributed under the terms of Sections 1 and 2 above on a medium
customarily used for software interchange; or,
c) Accompany it with the information you received as to the offer
to distribute corresponding source code. (This alternative is
allowed only for noncommercial distribution and only if you
received the program in object code or executable form with such
an offer, in accord with Subsection b above.)
The source code for a work means the preferred form of the work for
making modifications to it. For an executable work, complete source
code means all the source code for all modules it contains, plus any
associated interface definition files, plus the scripts used to
control compilation and installation of the executable. However, as a
special exception, the source code distributed need not include
anything that is normally distributed (in either source or binary
form) with the major components (compiler, kernel, and so on) of the
operating system on which the executable runs, unless that component
itself accompanies the executable.
If distribution of executable or object code is made by offering
access to copy from a designated place, then offering equivalent
access to copy the source code from the same place counts as
distribution of the source code, even though third parties are not
compelled to copy the source along with the object code.
4. You may not copy, modify, sublicense, or distribute the Program
except as expressly provided under this License. Any attempt
otherwise to copy, modify, sublicense or distribute the Program is
void, and will automatically terminate your rights under this License.
However, parties who have received copies, or rights, from you under
this License will not have their licenses terminated so long as such
parties remain in full compliance.
5. You are not required to accept this License, since you have not
signed it. However, nothing else grants you permission to modify or
distribute the Program or its derivative works. These actions are
prohibited by law if you do not accept this License. Therefore, by
modifying or distributing the Program (or any work based on the
Program), you indicate your acceptance of this License to do so, and
all its terms and conditions for copying, distributing or modifying
the Program or works based on it.
6. Each time you redistribute the Program (or any work based on the
Program), the recipient automatically receives a license from the
original licensor to copy, distribute or modify the Program subject to
these terms and conditions. You may not impose any further
restrictions on the recipients' exercise of the rights granted herein.
You are not responsible for enforcing compliance by third parties to
this License.
7. If, as a consequence of a court judgment or allegation of patent
infringement or for any other reason (not limited to patent issues),
conditions are imposed on you (whether by court order, agreement or
otherwise) that contradict the conditions of this License, they do not
excuse you from the conditions of this License. If you cannot
distribute so as to satisfy simultaneously your obligations under this
License and any other pertinent obligations, then as a consequence you
may not distribute the Program at all. For example, if a patent
license would not permit royalty-free redistribution of the Program by
all those who receive copies directly or indirectly through you, then
the only way you could satisfy both it and this License would be to
refrain entirely from distribution of the Program.
If any portion of this section is held invalid or unenforceable under
any particular circumstance, the balance of the section is intended to
apply and the section as a whole is intended to apply in other
circumstances.
It is not the purpose of this section to induce you to infringe any
patents or other property right claims or to contest validity of any
such claims; this section has the sole purpose of protecting the
integrity of the free software distribution system, which is
implemented by public license practices. Many people have made
generous contributions to the wide range of software distributed
through that system in reliance on consistent application of that
system; it is up to the author/donor to decide if he or she is willing
to distribute software through any other system and a licensee cannot
impose that choice.
This section is intended to make thoroughly clear what is believed to
be a consequence of the rest of this License.
8. If the distribution and/or use of the Program is restricted in
certain countries either by patents or by copyrighted interfaces, the
original copyright holder who places the Program under this License
may add an explicit geographical distribution limitation excluding
those countries, so that distribution is permitted only in or among
countries not thus excluded. In such case, this License incorporates
the limitation as if written in the body of this License.
9. The Free Software Foundation may publish revised and/or new versions
of the General Public License from time to time. Such new versions will
be similar in spirit to the present version, but may differ in detail to
address new problems or concerns.
Each version is given a distinguishing version number. If the Program
specifies a version number of this License which applies to it and "any
later version", you have the option of following the terms and conditions
either of that version or of any later version published by the Free
Software Foundation. If the Program does not specify a version number of
this License, you may choose any version ever published by the Free Software
Foundation.
10. If you wish to incorporate parts of the Program into other free
programs whose distribution conditions are different, write to the author
to ask for permission. For software which is copyrighted by the Free
Software Foundation, write to the Free Software Foundation; we sometimes
make exceptions for this. Our decision will be guided by the two goals
of preserving the free status of all derivatives of our free software and
of promoting the sharing and reuse of software generally.
NO WARRANTY
11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
REPAIR OR CORRECTION.
12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES.
END OF TERMS AND CONDITIONS
How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to the public, the best way to achieve this is to make it
free software which everyone can redistribute and change under these terms.
To do so, attach the following notices to the program. It is safest
to attach them to the start of each source file to most effectively
convey the exclusion of warranty; and each file should have at least
the "copyright" line and a pointer to where the full notice is found.
Copyright (C)
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
Also add information on how to contact you by electronic and paper mail.
If the program is interactive, make it output a short notice like this
when it starts in an interactive mode:
Gnomovision version 69, Copyright (C) year name of author
Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
This is free software, and you are welcome to redistribute it
under certain conditions; type `show c' for details.
The hypothetical commands `show w' and `show c' should show the appropriate
parts of the General Public License. Of course, the commands you use may
be called something other than `show w' and `show c'; they could even be
mouse-clicks or menu items--whatever suits your program.
You should also get your employer (if you work as a programmer) or your
school, if any, to sign a "copyright disclaimer" for the program, if
necessary. Here is a sample; alter the names:
Yoyodyne, Inc., hereby disclaims all copyright interest in the program
`Gnomovision' (which makes passes at compilers) written by James Hacker.
, 1 April 1989
Ty Coon, President of Vice
This General Public License does not permit incorporating your program into
proprietary programs. If your program is a subroutine library, you may
consider it more useful to permit linking proprietary applications with the
library. If this is what you want to do, use the GNU Lesser General
Public License instead of this License.