Started by isidoro, January 05, 2012, 06:23:20 PM
0 Members and 1 Guest are viewing this topic.
Quote from: prissi on January 05, 2012, 09:50:05 PMI would have dedicated way with their own system type for one way roads. Signs will be not correctly overlaid and quite ugly. Also the sign system will not work with drive on left, where the arrow would be next to the road.
QuoteAlso any crossing should not be blocked. It is also required by the law No honestly, hassle with two kinds of crossing is too much for 99% of the average players I fear. I fail to see an additional advantage from such a thing too.
Quote About reservations of your farthing (whatever this is, maybe the hobbits of Auenland?) Please use a better term which makes its meaning immediately clear. (sub_ribi_t?)
QuoteBack to reservations. I very very strongly advocate against it. They have be a constant pain with trains, and trains never ever disappear like that as citycars do frequently.
Quote But I see a conceptual problem: Overtaking times depend on the overtaker. The reservation ahead needs to be done by the overtaken. And it needs to be renewed every tile, since it can accelerate etc. I am not convined that this will not take much more CPU power than the easier check for free tiles would require. I am sceptic, but that can only be shown be implentation.
QuoteBut how citycars enter here? Citycars do not know where they go until directly at a crossroad. Then they choose an emtpy way at that time. Thus the could never reserve a way in advance and any prediction of overtaking and the like is difficult.But maybe I have misunderstanding here.
Quote from: isidoro on January 05, 2012, 11:46:55 PM And sometimes, the convoy may have reservations in two tiles...
Quote from: isidoro on January 05, 2012, 11:46:55 PMDo you mean a new weg_t::system_type instead of a weg_t new flag? I don't understand the difference between them very well. Please explain.
Quote from: TurfIt on January 06, 2012, 03:28:10 AMWhat is the purpose of adding flag: weg_t::IS_ONE_WAY? i.e. where would it's value be useful? If the ribis are set, the info is already there.
QuoteSmooth lane changes. Fine, but if applied to the regular overtaking, then it would have to start the transition a tile sooner such that it's already in the overtake lane before entering the tile with the overtaken. And similarly at the end when transitioning back will need an extra tile there too. Extra required tiles will reduce the chances of an overtake even more.
Quote Crossroads (intersections as I call them). Reservations were certainly something I considered when overhauling the weg_frei and no_cars_blocking routines. There's some cases still where cars can end up where they don't belong that would easily be solved by use of reservations. But those cases are generally rare and not overly impactive when they do occur, hence the trouble of adding a reservation system wasn't worth it IMO. For implementing avenues, it might be the only feasible way to simplify the logic some, but they bring a whole host of issues along with them. An extremely detailed plan is strongly suggested before starting down this path. (save/load is a huge issue).Actually they may have reservations in 6 tiles. Consider a road train convoi made up of 4 16 length vehicles on the diagonal...
QuoteYour Farthings are too simplistic, even for plain two way roads. Consider a Northbound car turning left, this reserves the SE and NW Farth. Eastbound and Westbound right turners can still reserve NE farth, SW farth, and share the intersection. Great. But a Eastbound left turner would also grab SW and NE farths and proceed despite that movement being in conflict with the northbound left turner. More farths are required to handle this. Now go through all possible paths with the various one-way, two-way roads intersections identifying all conflicting/non-conflicting and .....
QuoteFor intersecting avenues, a 2x2 block of tiles is what forms the 'real' intersection. The reservations must extend through that.
Quote All intersections *MUST* be non-blocking.All intersections *MUST* be non-blocking.Again? All intersections *MUST* be non-blocking. Nobody enjoys trying to untangle a deadlock caused by cars moving to places they shouldn't. If you do, have I ever got the map for you.
QuoteHow are diagonal roads handled? Remember internally there are no real diagonals, just tiles zig-zagging. In your diagram, the S tile, Central tile, and E tile could be just that forming a 90 deg turn, or the exact same tile layout may be part of a diagonal road instead. The allowable paths through the tile would be different for the two cases. e.g. For the diagonal road, both lanes need to move straight. Car in S lane through SE farth ending up in E lane simultaneous with a car in S* land through SW Farth and NE Farth ending in E* Lane. However, if this is a 90 deg intersection instead, then the car in S lane might go SE Farth, NE Farth, N lane. Now the car in the S* lane must be forbidden from making the right turn into E* lane as that conflicts with the other cars movement. My point here is that identical tile layouts require different movement rules. How can this be detected and handled?
Quote from: Dwachs on January 06, 2012, 09:12:10 AM[...]My idea to construct one-way roads: Create a special sign 'Start of highway', all road tiles after this sign automatically become one-way. Imho the gui & construction discussion can be postponed to the point, where the actual movement code is ready.
QuoteA new more fine-grained reservation system for roads may allow vehicles driving closer to each other. In particular in traffic jam situations.
Quote[...]In the preparation phase, we could also make a massive translation of German code entities.
Quote from: prissi on January 06, 2012, 09:43:24 AMAbout the farthing: I had to maintain once a program with stuf named Max, Moritz, Important, ...It is fun at first, but were off pretty quickly. ALso farthing is only gasp by native british, I fear, since I have no idea what you are talking about. Even though I read Lord of the rings but the german edition.
QuoteThe original parts of the Shire were subdivided into four Farthings ("fourth-ings" or "quarterings"): the Three Farthing stone marked the point where the borders of the Eastfarthing, Westfarthing and Southfarthing of the Shire came together, by the East Road.
Quote[...]An another thing you did not mention at all: How would you distribute cars between those two lanes? I think this is most important for a working system.
QuoteIn fact, my idea is quite simple to implement: a car follow its route in its present lane, if it finds a car ahead and it is a two-way road, nothing is changed from present behavior, tries to overtake or stops. If it is on a one-way road, it looks if it can change lane and, if so, it does.This can be refined with a sort of gravity that makes the cars return to the right lane when possible... Since transitions (change of lanes) occur one per tile maximum, the car is not going to continuously bounce from one lane to the other...
Quote from: prissi on January 06, 2012, 09:32:40 PMThus cars will try to go on the right lane again when passing has ended?
QuoteHow a car determines if the left lane is free. It will just ignore traffic behind and go left or will it also look backwards?
Quote from: Dwachs on January 06, 2012, 09:12:10 AMA new more fine-grained reservation system for roads may allow vehicles driving closer to each other. In particular in traffic jam situations.
Quote from: Dwachs on January 06, 2012, 09:12:10 AMIn the preparation phase, we could also make a massive translation of German code entities.
Quote from: isidoro on January 06, 2012, 03:16:03 PMThe interpolation may be changed to accommodate for that. For instance, an end of overtaking transition This patch is five lines long to do and it doesn't interfere with the rest of the code. If you agree, I can give it a try...
Quote from: isidoro on January 06, 2012, 03:16:03 PM I like the word crossroads to clearly separate that from crossings of two different way types.
Quote from: isidoro on January 06, 2012, 03:16:03 PM And also I would not call my method reservations. It is more an occupation, since the vehicle is really there.
Quote from: isidoro on January 06, 2012, 03:16:03 PM If you look closely to the example table of my first post, for a car heading north (hence coming from the south), the S->W transition reserves three subtiles
Quote from: isidoro on January 06, 2012, 03:16:03 PM to avoid that. Not all cases are taken into account, but your present system doesn't either...
Quote from: isidoro on January 06, 2012, 03:16:03 PM It is more a replacement for no_cars_blocking and parts of ist_weg_frei than the whole of the latter.
Quote from: isidoro on January 06, 2012, 03:16:03 PM So you example doesn't make sense. A car coming from south and turning east will occupy SE subtile only. A car going from S to N, occupies SE and NE, and so on. Diagonals are not a problem since they are only a painting-trick (from the point of view of the motor of the simulation, the vehicle is really going zig-zag and occupations are made accordingly).
Quote from: isidoro on January 06, 2012, 03:16:03 PMThis can be refined with a sort of gravity that makes the cars return to the right lane when possible... Since transitions (change of lanes) occur one per tile maximum, the car is not going to continuously bounce from one lane to the other...
Quote from: isidoro on January 06, 2012, 11:30:47 PM On the other side, in cities, driving lanes depend more on the route you intend to follow, but I don't know if that would be easy to simulate without looking too far in the route and wasting some precious CPU time...Maybe that is a task for normal steps (not sync steps) to calculate and being cached in a variable of the convoy (something like lane_affinity)?I haven't thought about this until you have pointed out.
Quote from: isidoro on January 06, 2012, 11:30:47 PM Occupations may be used again. Upon entering a new tile, if the car cannot go forward and the other lane in the tile the vehicle is in and the following tile are free, then occupy the relevant subtiles of the latter tile and change lines.
Quote from: TurfIt on January 07, 2012, 02:59:50 AM[...]If you mean the German comments, sure. If you mean renaming variables, to what end? IMO they're fine as is. I still haven't sorted back out the half-assed renaming of einstellungen to settings... Now instead of just einstellungen and umgebung to keep straight, we get a third one (settings) to remember.
QuoteI see... cheating then! A faster transition would certainly reduce the probability[...]
Quote[...]But I get what you're trying now, although am now unsure how occupations have a problem with stale reservations...
Quote Also, as occupations mean the vehicle is currently in that position, I don't see the gain from using farths. Just query the vehicle?
Quote Which would then needlessly block the E*->N path.
Quote Do you have an example? convois only as citycars are still in a world of their own!
Quote I think from a performance standpoint, best to stick to the current system of calculating the info as required. The farth proposal does have the attraction of simplifying sections of these routines, but at the cost of updating the occupancy status on each tile for each convoi as they move, even if that information is of no current use since no other convois are nearby. Maybe the farth info would fit into a structure that's being accessed anyways, and hence be readily available in the cache anyways, probably not though. There's really no room to add things requiring extra memory accesses at the moment IMO.
Quote A car travelling the NE direction actually travels N>E>N>E>N>E and so on. In this case, we have a straight diagonal road. I would expect cars in both lanes to be able to travel side by side straight down this road. In you diagram, this corresponds to S->E for the car in one lane and S*>E* for the other. No problem.
Quote The same tile layout as this diagonal road could instead be an intersection. S>E is still valid for a car in the right lane to make a right turn. S>N is also valid for straight through. S*>E* which was valid for the diagonal is no longer ok for the intersection. Turning right from the left hand lane is forbidden.How to handle this detection of allowable routes given the same tile layout?
Quote [...]Some scheme that avoids the car just stopping would be better. If it starts trying to change lanes several tiles before it must be in the lane, that might work. Then only stopping when it must.
Quote Of course cars coming up behind might then change lanes to pass the stopped car. Or worse, two cars stopped side-by-side each trying to change to the others lane! Lot's of little issues like this to contend with.
Quote from: isidoro on January 07, 2012, 12:31:36 PMIf sometimes vehicles overlap a little, that is not news in ST.
Quote from: isidoro on January 07, 2012, 12:31:36 PMIf you don't use occupations, you have to query all the vehicles in the tile, look for directions, etc. With railways everything is simpler because we have only one lane per tile.
Quote from: isidoro on January 07, 2012, 12:31:36 PM I guess that you mean E->N is needlessly blocked in a S->W movement. E*->N must be blocked by all means. I don't see here such a big problem. Moreover, what is your alternative for crossroads with different type of roads arriving at them and still sometimes a transition is by all means needed because the road the vehicle is going to is a two-way road?
Quote from: isidoro on January 07, 2012, 12:31:36 PM You said that. And I mean all kind of traffic, not just convoys.
Quote from: isidoro on January 07, 2012, 12:31:36 PMBut I would say more... Performance issues come in very big maps with a lot of traffic.
Quote from: isidoro on January 07, 2012, 12:31:36 PM This has nothing to do with the issue in hands.
Quote from: isidoro on January 07, 2012, 12:31:36 PM I don't think that is much different from current behavior. Cars stop in Simutrans when they cannot advance.
Quote from: TurfIt on January 07, 2012, 08:16:37 PM[...]I'm back confused between occupations and reservations again...For occupations, are the subtile positions (formerly called farthings) marked as occupied only when a vehicle is actually on the position?Or, when a vehicle enters a tile, it marks all subtile positions required for its journey through the tile as occupied? aka reserverations.
Quote[...]To develop the current ncb routine, I mapped out all possible paths through the intersection,[...]
QuoteAdding oneway roads to the mix just means mapping out even more paths. Many more.
Quote[...]Thus far, profiling shows the performance degradation on such maps is due to routing the sheer number of passenger rather than moving the convois needed to move them.
QuoteEverything to do with it...Refer to attached picture. One way roads, allowable paths marked. The circled intersections are identical, ribi=7. Yet the allowed paths are different.
Quote Yes I mean vehicles should not be turning across lanes. Simutrans traffic laws should be based on some semblance of order.
Quote [...]Have you ever played Cities in Motion?[...]
QuoteP.S. Could you try leaving two blank lines after your text before the start of the next quote? [...]
Quote from: prissi on January 07, 2012, 08:41:45 PMSorry could not resist: First you wanted to remove all german, yet suggested farthing, which was again very cultural ... it is not easy to be consistent.
QuoteAnd so far we had about 12 german developer and about four non-german; and since 2004 most new stuff is in english.
Quote [...]Imho subtiles (farthing) could be mapped directly from dir via an array.[...](That way will be consitent with diagonals imho, or?)[...]
Quote from: isidoro on January 08, 2012, 03:57:33 AMThey are occupations but with a tile grain, at least at the beginning if you don't want to go further in as Dwachs suggested.
Quote from: isidoro on January 08, 2012, 03:57:33 AMI put four simple subtiles to do it easily. Think that one can put another subtile centered in the tile if needed, or even more if needed. Moreover, subtiles may not represent the same space when on a diagonal tile if wanted.
Quote from: isidoro on January 08, 2012, 03:57:33 AM I think that you are not getting it at all (either that or I'm too blind to see your point).
Quote from: isidoro on January 08, 2012, 03:57:33 AM In the picture you have attached, we have two options, even if we have the same ribi (=7, if you are right). If you mean that all your paths should be allowed at the same time and subtiles don't allow them, you should consider that a vehicle coming from S in the above picture either goes to N or goes to E. It cannot go to both at the same time! So that possibility is right to be forbidden at the same time. The same applies to the below picture, but even worse, why didn't you mark the other possibility for the blue arrow, to go to N besides going to N* and E*?
Quote from: isidoro on January 08, 2012, 03:57:33 AM But that is something to be enforced somewhere else, not by subtiles...
* North tile ** * * *********************** * * * * | * * NW TN NE * * Farth. | Farth. *West tile *-TW-----+--TE----* East tile * SW | SE * * Farth. TS Farth. * * | ** * * *********************** * * * * South tile *
Quote from: TurfIt on January 08, 2012, 04:41:14 AMSorry but I still don't have a clear picture of what you're proposing here.Can you provide an example with a vehicle approaching the intersection, and moving through it until it exits detailing its motion, the occupation statuses as it moves, and what other vehicles that might be approaching would be seeing?
QuoteObviously the vehicle can't go both ways at once... Where did you come up with that? I'm showing the possible paths a vehicle could take.
QuoteOn the diagonal road, I show the left lane vehicle only allowed to turn left into the left lane. Making a turn into something other than the closest lane is illegal in any civilized place.
Quote[...]But, I'm also looking big picture at all the elements that are needed to implement oneway roads. The proposal I've seen so far covers maybe 10% of what's needed; The vehicle movement part which is relatively trivial. Where's the rest?
Quote from: Dwachs on January 08, 2012, 10:10:26 AM[...]The check whether a given path blocks the crossroad can be computed / precomputed too.[...]
QuoteThe occupation flag is set on all subtiles on the vehicles path (?). (Does this replace the no_cars_blocking routine ?)
Quote from: Dwachs on January 08, 2012, 10:10:26 AMThe occupation flag for a subtile is cleared when the convoy leaves the subtile.The occupation flag is set on all subtiles on the vehicles path (?). (Does this replace the no_cars_blocking routine ?)
Quote from: Dwachs on January 08, 2012, 10:10:26 AMIf a train on a tram track is on the crossroad (or has reserved a block on its track across the crossroad), then cars cannot cross the tram track, thus blocking certain paths between subtiles.
Quote from: isidoro on January 08, 2012, 06:42:31 PMThen, the first one to arrive at the crossroads will check if the crossroads is not occupied and will mark its path subtiles as occupied and hops. The rest will see that their desired path is not possible and stop.
Quote from: isidoro on January 08, 2012, 06:42:31 PMBut subtiles does not prevent deadlocks in itself. They are not intended for that. They must be combined with something like your 4-tile checking to guarantee that no vehicle will have to stop at the crossroads and, thus, deadlocks. The two things are different and compatible...
Quote from: isidoro on January 08, 2012, 06:42:31 PMBut, as Dwachs says, we know in advance which of them the vehicle is choosing when entering the crossroads... There is only one certain, real possibility, isn't it?
Quote from: isidoro on January 08, 2012, 06:42:31 PM Well, your example below will hardly be built in any civilized place, I guess. When in a one-way road, exits are on the right, not on the left... Precisely to avoid those dangerous lane crossings... But you would be amazed the kind of things I've seen built in the supposed civilized places.
Quote from: isidoro on January 08, 2012, 06:42:31 PM To name a funny one (I will omit the name of the country), a town wanted to build a big roundabout to deal with traffic in a dangerous intersection.
Quote from: isidoro on January 08, 2012, 06:42:31 PM If this is only the 10% I don't dare imagine what would be the other 90% of this delivery...But you know: every long journey begins with a first step...
Quote from: isidoroQuote from: Dwachs on Today at 11:10:26 AM [...] The check whether a given path blocks the crossroad can be computed / precomputed too. [...]All your post is what I try to explain... but this point I don't understand. What is a path that blocks the crossroads?
Quote from: TurfItWeren't trams changed a while ago to be completely independent of road vehicles?While I'm all for trams getting stuck in traffic too, shouldn't be undoing something that was specifically previously changed...
Quote from: Dwachs on January 08, 2012, 08:36:01 PMAny other path through this crossroad is blocking.
Quote from: Dwachs on January 08, 2012, 08:36:01 PM I must have missed this completely. I could not find any checks regarding interaction cars <-> tram in the code
Quote from: Dwachs on January 08, 2012, 08:36:01 PMLane affinity: imho these decision should be made in the driving code, not in route finding. Overtaking is also not decided during route-finding.
Quote from: TurfIt on January 08, 2012, 06:45:24 PM[...]On the subject of my issue with 'identical' intersections yet different allowable paths:How about a second set of ribis for the second lane? [...]
QuoteWhichever method is used for identifying allowable intersection paths, the route finder is going to need changes to utilize this information anyways. I don't see how the original proposals claim of the routing algorithm being untouched can be true.
Quote[...]And finally - station stops.Should they be allowed on the left too? or only the right (driving side)?If forced to be on the driving side only, then a stop on a tile immediately after an intersection turn could be trouble; The vehicle would be in the wrong lane and need some exemption from the traffic laws to allow turning into the far lane...
QuotePlease don't talk about roundabouts. Next someone will want them in Simutrans too.
Quote from: Dwachs on January 08, 2012, 08:36:01 PM[...]Consider this sketch:[...] N* N* | ** | ** ******** E* lane* E lane* ******** | ** | * S S*
QuoteLane affinity: imho these decision should be made in the driving code, not in route finding. Overtaking is also not decided during route-finding.
Quote from: prissi on January 08, 2012, 09:38:56 PMAt hop_check()[...]
QuoteOk, so far so good. What about more than one crossing? I that case hop_check needs also the reserve the subtiles on the next crossing an so one[...]
QuoteBut one thing is not clear, and I think that turfit was also mentioned it. How does the sub_tiles for lane change on diagonal road look like? Any such subtiles would be identical to the already left lane traffic? Or not?
Quote from: isidoro on January 09, 2012, 01:38:49 AM Just click on the arrow button (the last at the line before the emoticons) and you get the previous editing behavior.
Quote from: isidoro on January 09, 2012, 01:38:49 AMI don't think that a second set of ribis is a good idea. The ribis on the adjacent tiles can tell you, if wanted what happens in the other lane.
Quote from: isidoro on January 09, 2012, 01:38:49 AMI think nothing needs to be touched in route finding.
Quote from: isidoro on January 09, 2012, 01:38:49 AMAnd two bits can be hidden anywhere in koord3d...
Quote from: isidoro on January 09, 2012, 01:38:49 AM if one doesn't want to go into the other lane, if wanted. Although I would allow all cases without problems.
Quote from: isidoro on January 09, 2012, 01:38:49 AM the routing code may add for road routes one of these hints: Drive to the lane you wantGo to the right the sooner you can, but don't stop if you can'tGo to the right right now in this tile or stopGo to the left the sooner you can, but don't stop if you can'tGo to the left right now in this tile or stopThis would allow the car to freely choose the lane while driving based on the traffic with some hints or obligations based on its route, not being too CPU intensive.
Quote from: isidoro on January 09, 2012, 01:38:49 AMMy opinion here is that the check should include some tiles ahead (like TurfIt's routine), but the reservation is only done in the next tile.
Quote from: isidoro on January 09, 2012, 01:38:49 AM Even if you keep all intersections free, there can be a deadlock. So why bother with all that complication? Check some tiles and occupy only the next.
Quote from: prissi on January 09, 2012, 09:29:45 AMI would not use lane changes on crossings. And for turning right, the car has to be on the right lane in most countries, so keep this simple
Quote... and we can use a table for lookup table of subtiles on turning (if one uses an extend fahrtrichtung with 16 directions. It would make several stuff simplier. Why do no one comment on that?)
Quote And if one start with reserving subtiles, it should be consequently at least four crossings ahead. (And then the driver could not see farther anyway ... ) ANd then keep them to may ist_weg_frei much less CPU hungry and easier to understand.
Quote And adding stuff in route finding for cars is clearly not my favourite. Also extending koord3d will immeadiate increase memory foodprint of every structure by 4 bytes, clearly is not a good idea.
Quote A car could check itself upon entring a way has IS_ONE_WAY system type when it will leave this way and to which side, or if it has a stop on the way. It set then a route index (exit_oneway_index) and the side (LR). Before if can move freely. With such an route_index, it can also estimate, if it can pass a car and so one, i.e. all overtaking checks would be simplier.
Quote from: IsidoroI see a lot of headaches and also memory consumption there. The more you reserve the more likely you get to a deadlock...
Quotealthough I think that a new system type is now preferred by them against a new flag, I don't understand if this make one-way roads incompatible with elevated roads or not
Quoteallowed or denied change of lines in crossroads. The general tone I feel is that some of them should be prohibited, but I don't see it. Another reason against it: the player may have changed the configuration of a crossroads while a vehicle has already entered a one-way road leading to it. The vehicle has already decided to which lane to attach at the entrance of the old crossroads configuration. What has to be done when it arrives to the new crossroads that force a forbidden change of lanes there? For example, a one-way road was changed to a two-way and the lane the car wanted to go is now forbidden...