Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Put passengers on trains #5

Open
golvok opened this issue Sep 7, 2015 · 1 comment
Open

Put passengers on trains #5

golvok opened this issue Sep 7, 2015 · 1 comment
Assignees
@golvok

Comments

@golvok
Copy link
Owner

golvok commented Sep 7, 2015

right now nothing decides what passengers go on which trains.

Also nothing in the animation shows this. :P
@golvok golvok self-assigned this Sep 25, 2015
@golvok
Copy link
Owner Author

golvok commented Sep 27, 2015

There are still some problems...

Search algos usually require iteration over all the out-edges of a vertex, but we really can't provide all of them - technically there could be an infinite number of them - so we must do something to trick the search algorithm.

My first idea

Have dummy nodes with high cost that are returned at some point that are the same node, but are some time later (wherever we decided to cut it off). The search algos then would only come back to this node after looking at all the other ones, in which case the same thing would happen - a few would be returned, then a node that doesn't go anywhere, but does increase time.

Second idea

Out-edges of a vertex could be defined as where the trains that leave now go next and the next time interval (but at the same location). This has problems if we want to use a real number for time - would have to do intervals, which I guess is OK. Also, this would greatly increase the number of vertices, which is kinda bad. Finally, with intervals, it's really the same idea as the first idea, except that the intervals would be really small.

Other TODOs

  • related - make the rest of the algos understand time.
  • make a distance heuristic?
  • fix the "infinite out-edge" problem, above.
  • animate passengers

golvok added a commit that referenced this issue Sep 27, 2015
@golvok
now does passenger routing! uses a-star search on an implicit graph
221056a 
partial fix for #5

No heuristic for now...

The implicit graph is determined from the Schedule & the TrackNetwork. Each
"vertex" is a pair of TrackNetwork::IDs and a time. Out edges are determined
from trains that leave in the future, and a corrisponding "vertex" is the
pair of the next ID the train goes to, and the time it gets there.

Still has some problems: the search algorithm needs to iterate all the out-edges
of a vertex, but this technically will be an infinite number. Need to come
up with a way to "hide" all except a small finite number.
golvok added a commit that referenced this issue Sep 28, 2015
@golvok
now does passenger routing! uses a-star search on an implicit graph
0ad0c41 
partial fix for #5

No heuristic for now...

The implicit graph is determined from the Schedule & the TrackNetwork. Each
"vertex" is a pair of TrackNetwork::IDs and a time. Out edges are determined
from trains that leave in the future, and a corrisponding "vertex" is the
pair of the next ID the train goes to, and the time it gets there.

Still has some problems: the search algorithm needs to iterate all the out-edges
of a vertex, but this technically will be an infinite number. Need to come
up with a way to "hide" all except a small finite number.

code loosely based off of http://stackoverflow.com/a/9782649/2256231
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@golvok golvok

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@golvok