Started by jamespetts, March 24, 2012, 12:16:18 AM
0 Members and 1 Guest are viewing this topic.
QuoteSecondly, how would a system like this evolve to be able to have the in-game representations of citycars actually following a route from their origin to their destination?
Quoteagain, quickly for the moment, a normalised model will not work, as we need absolute numbers to generate realistic traffic congestion levels: the number of private cars for any given level of usage should have a realistic and determinate relationship to the number of 'buses required. [...]
QuoteAs to the *ed point, there is no general assumption that private car owners take the train when it is faster: the decision as to whether to use a private car or public transport is a multi-faceted decision, of which only one element is the relative journey times of both modes. This is realistic.
Quote from: prissi on December 10, 2012, 12:36:18 PMBut currently only one map is sent to the clients. You would need to transfer the map then to all clients connected. You would also need two independent random counter.
QuoteAdditionally server usually have much weaker CPU than clients as CPUs are shared. Even if you have a single CPU, it could mean that this is rather a single core out of 16, and hence features like turbo boost and similar are disabled. If you can do a hard reset of your server, then the chances are high this is really and independent dedicated server. But those come still with a 100 EUR/$/GBP tag per month.The display is anyway threaded and is not the largeast CPU consumer for developed games is standard and likely also exp.
Quote from: jayem on January 02, 2013, 11:02:46 PMYou could model Factories/Shops and Attractions as absorbing cars (valleys of car potential), and Houses as (hills) emitting them to neighbouring roads.
Quote from: jamespetts on January 02, 2013, 11:19:53 PMThis is fine for a congestion modelling algorithm, and also suffices to check whether residential areas are connected to somewhere useful, but in Simutrans, we need to check whether people can get to the specific places that they want to go, rather than just anywhere.
Quote from: jamespetts on January 02, 2013, 11:19:53 PMTo be a step forward, a private car routing algorithm would have to give an accurate network based answer to the question, "can packet of passengers X get to its destination within its journey time tolerance?" rather than make assumptions.
Quote from: inkelyad on January 03, 2013, 04:47:01 AMIt is quite possible. You need to model separate 'heat plate' for each attraction/factory.As time go catchment area for factory will grow => more calculations.But number of factores/attractions should go down too (factories tends to be bigger over time).
Quote from: jamespetts on January 03, 2013, 10:49:14 AMI am not sure that I fully understand. How would this integrate with the current passenger generation system which generates specific packets of passengers at specific buildings wanting to go to other specific buildings (often in other towns) and needing to know whether they can find a route there either by private car or player transport
Quote, and, if by both, which is preferable? We need to be able to simulate the exact same journeys that passengers make by player transport being made by private car if the passengers make the private car modal choice.
Quote from: inkelyad on January 03, 2013, 01:43:56 PMUhh... sorry, I was thinking about another decision function. Not 'which transport is faster?', but 'which transport give me better probability to reach destination in time?' It is not same.
Quote from: jamespetts on January 03, 2013, 02:28:07 PMDo you have any thoughts on whether my posited optimisation of route-finding might work within acceptable limits of performance?
Quote from: The paperSince the size of the link table is often larger than the capacity of the main memorybffer of a given GIS system, the link table may need to be stored on a secondary storage device,typically on disk. While state-of-the-art database engines may attempt to cache the link table intomain memory during path evaluation, this will generally not be feasible due to size constraints.3In this case, many tuples links in the link table may need to be retrieved over and over againfrom secondary storage and placed into the main memory buffer for evaluation. Given that suchI O operations on most modern computers are typically several 100-fold more expensive than CPUoperations, the I O costs are the dominant factor of path computation costs.The high processing costs are thus incurred by the recursive nature of the graph traversalcomponent of path query computation. Resolving embedded constraints may further increase I Ocosts significantly. For example, in a related e ort 17, 18, 22, 23, 19, 20 , we found that processingspatial constraints see Q3 path query is very I O intensive. Thus such constraint resolutioncompetes with the path finding component of the search process for computational resources suchas the buffer space. This further motivates our research presented in this paper on optimizing thepath computation process by reducing I O activities.
Quote from: jamespetts on January 03, 2013, 06:49:54 PMIs there any way of knowing (without incurring the incalculably vast amount of time required actually to code both versions from the ground up), or at least, making a sensibly educated guess as to, how pre-calculating the distance between cities per se will work as an A* heuristic?
Quotenot at all uncommon case of an origin point in one city being nearer the destination point in another city than either is to its own city hall
QuoteAs to the paper, have you looked at it in any detail? The abstract mentions a number of different techniques; do you think any of them suitable for what we need for this purpose?
QuoteThe issue being discussed here is that the complete set of nodes and links for the sort of system discussed in the paper cannot be stored in memory at once, hence requiring frequent disc accesses. It also assumes a model of nodes being intersections and links being the roads between them, which is different to the Simutrans tile based model, in which every road tile is a node, and the connexions to its neighbouring tiles are the links. In Simutrans-Experimental, the issue is not that each individual query takes a long time (what is described as the "spacial query" at Q3 is not relevant here because the links themselves do not have any special characteristics relative to one another) due to IO access, but that there are vast numbers of queries that have to be processed in a short time. The issue is CPU-intensiveness rather than memory size or bandwidth.
Quote from: jamespetts on January 03, 2013, 07:35:00 PMAhh - do you imagine calculating and storing the distance to each city hall from each road tile? With 500 cities, that would be a very large amount of calculation - are you sure that this would help?
QuoteIndeed, perhaps I am missing something, but does a distance to the destination city hall heuristic actually add anything to the distance to the actual destination heuristic? Is it any better? Or is the point that the calculating of the distance to X from each tile is the part that takes most of the computational effort such that pre-calculating this once for every road tile would reduce the work of doing 300,000 A* searches enough to bring it within reasonable performance limits?
Quote If that is so, then would my system not do the same?
Quote from: inkelyad on January 03, 2013, 07:54:15 PMI can be wrong, but my memory tell me we already do this.
QuoteIt is one fill from Dijkstra's algorithm for each city hall.
QuotePre-calculated distances to halls will lead A* straight to destination city ( first to to source city boundary, then to destination city via shortest path). There will be no backtracking there.You need to find and copy stored inter-city path. It almost same as reconstruct it via A* with right heuristic.
Quote from: jamespetts on January 03, 2013, 07:58:57 PMI really don't think that this is done in Simutrans - where are these data stored, do you think?
QuoteMight this not make placing new roads unresponsive on occasions if this has to be done every time that road tiles are laid, for every single tile?
QuoteBut, in this case, we have to keep in memory all the road to city hall distances on top of the complete set of routes, whereas, in the system that I proposed, we only need to keep the complete set of routes. Does your system not take more memory than mine...?
Quote from: inkelyad on January 03, 2013, 08:42:41 PMIf we do it for every single tile, yes. But do we really need to?
QuoteIt depends.'each tile would be checked to see whether it also contains a route to the destination building.'Each tile will be storing routes. It is not clear what will take more memory.