tiny timetable patch / 簡易タイムテーブルパッチ

[wackdone]

電車の中でコードを睨んでいたら、時刻表まわりのバグがだいたいとれてきました。
(通勤途中にコーディングはできても、Simutransをテストランさせるのは何故か恥ずかしくてできない 
真夜中になる前には最新版をリリースできると思います。

[wackdone]

皆様への返信を書いてる途中でXがいかれてしまったorz
すみません、手短か版になります。

gonyoさん：
ぜひとも、Simutrans+TTTダイヤ追求講座を、Wikiに開いて頂きたい
上限密度  (正確に言えば、密度は時間の逆数ですね) を、近似的に求めることは可能です。
精度を高めたければ、各列車が(積載量は最高か中程度か空荷か選んだとして) どの区間をどのように走行するか事前計算して
「これ以上早くできない」という各列車の区間時間の集合を準備します。(個々の列車の理想走行が決まる)
そして、今いる順序で無理に走らせたらどうなるかをシミュレートします。
(ボトルネックを見つければいいので、NPではなくP問題に落とせると思う。)
で、詰まったところにどれくらいマージンを入れていけばいいか、簡単な最適化問題で解いて、
出てきた総マージン量の逆数が限界密度になるんじゃないかな。

と書いてみましたが、gonyoさんの言うように、実際の線路設備の影響の方が大きいですし、
実際に人間が見て納得するような結果を出す解法に育てるまでには、ずいぶん手間がかかるでしょう。
そして何より「シミュレーションの上で上手く走らせるために、さらにシミュレーションしてどうすんの?」という話があります LoL
(まあ、偉そうに書きましたが、正直、そんだけコード作るのしんどいなあ、というのが本音です、はい )

今だと、時間制約を全部とっぱらってみて、実績時刻を時刻表ウィンドウ上で眺めてみることで問題がわかってこないかな?
そのためには、表示している情報が足りない気もしますが。
例えば、各列車が始点を実際に出発した時刻がわからないと (今はこの情報は出ていない。あくまで計画上の始点出発時刻を使っている)
列車間の関係はわかりませんね。
これに限らず、ダイヤを組む(あるいは線型改良するなど)人の何か助けになる情報を拾って表示できるといいのですが。

[wackdone]

sima0222さん
示して頂いた表は、現状の TTTで表示させると、という話でいいですよね?

一応、よくある簡単なアルゴリズムでそこそこ良くなる版のコードは、手元で眠っているのですが
少し改修して次の版に入れられればと思います。
「基本路線」つまり、pivotを置いて、そこを中心に描くというのはありですね。
あわよくば、表示途中でpivotを再設定して構成しなおすが出来るともっといいのかも。
基本のロジックが固まれば、そこはUIとしての作り込みで進められます。

さてその基本ですが、根本的には、単方向エッジの集合でできたグラフを、脳内で双方グラフに再構成しつつ、
結局はベクトルに落としこまなきゃいけない、という数学的にも結構派手な話なので、
完璧なアルゴリズムを見つけるのは簡単ではないでしょう。
(すでに世間に出ている論文などご存知の方いらっしゃいましたら、教えて頂けると助かります。)
「スケジュール」という形で、各エッジの間には時間的前後関係があるため、これをグラフ上でどう扱うかも問題です。
また「スケジュール」から読みとれるグラフの中には存在しないノードを作り出さなければならず、
このためには、下に示す区分けのうちの(1)が出てくるので、完全に位相空間だけでは取り扱えない。
そもそもグラフと捉えているのが問題だろうか。。。

また、この問題は以下に示す2つの問題に分割でき、それぞれの精度(あるいは人間の期待に沿うか)を出すのが難しいです。
 (1) 点 A、B、C が与えられた時に A から C へ移動する時にBの近傍を通過するかを判定する
    (乗り物の事情に合わせた判定がされなければならない)
 (2) 上の(1)を使用して、既にある点のリストの中に、新たな点を挿入する場所を決定する
      また、リストの各要素には (その点間の距離を計測するために) 他の要素との接続関係が記録されなければならない
      (単方向でよい。ただし接続先はどれか１つの要素に絞らなければならない)

(1)の方は頻繁に使用されるので、できるだけ軽い内容であって欲しい。(というわけで今は距離関数を定義してシュワルツの不等式で簡単に判定)
(2)の方は、三乗オーダのアルゴリズムならそこそこあるのですが、 編成のスケジュールを舐めながら、かつ速くしたいので、
 できれば線形オーダに毛が生えたくらいであって欲しい。
という要求がきつくって。。。
あとは「場合分け」をできるだけしたくないという私のロジック屋としての性格の問題かな。

特に(2)の方は、パズルとしては楽しめると思うので、参加者募集です。

[wackdone]

yoyoさん、VCの件了解です。

_tつきの定義が無いなんて。POSIXじゃなかったっけ? まったくMSは。。。 という愚痴はおいといて直します。
"*/*"を１つのトークンとして認識するなんて、いったいどんなパーザ書いてんだよMSの連中は。。。という愚痴は(以下同文)

innerの件は、コンストラクタでやってしまわないとinsecureなんですよね。
本当は、outerへのポインタは const メンバーにしたいくらいなので。
(innerからouterを指すポインタが途中で変化してしまっては、innerクラスとは呼べないだろうというわけで。)
また、outerインスタンスへのポインタが定まらないデフォルトコンストラクタも廃絶しないと、危険ですし。
timetable_view の更新判定が成長してきたので、そろそろちゃんと Model と View の分離をやって、
その暁には inner class は廃絶できると思いますので (残りは contained by linkだけにできる)、もうしばらく我慢してやってください。

bits_per_day は、誘惑があるのですが、bits_per_month の廃止はできないですね。
廃止してしまったら本家の機能の改変にあたるので、まず本家に入れてもらえなくなると考えていいと思います。
やるとしたら、TTT用だけの bits_per_dayを準備して、TTTで見える姿だけ変える感じですかね。
ticksそのままでUIだけ、というのは、そういう意味でおっしゃってたのかな?
まあ、昼夜の表示の切り替えも、bits_per_month にもとづく1日の中で行われているわけではないので、
いいのかなあとも。

[kanedai]

電車を走らせて、1周程したときに時刻表を表示して実績時間を選択したらえげつない数が出てきました。

[wackdone]

とりあえず今の段階で確認。
「自動再計算」を有効にしている列車ですか？

[kanedai]

何も設定せず環状線を走らせただけです。
積荷待ちも設定せずです。

[wackdone]

「何も設定せず」というのは、TTTに関する設定も一切なし？
それとも、
  (1) 駅間計画時間だけは設定している
  (2) 運行周期と始点発時刻だけは設定している
  (3) 上の(1)と(2)を設定しているが、それ以外のパラメータは一切設定していない
のいずれか？

あと、「えげつない」数字が出てきたのは時刻表の上のことだと思うのですが、
  (a) 計画時刻 (黒文字) のところに出てきた
  (b) 実績時刻 (オレンジや赤)のところに出てきた
  (c) それ以外のところに出てきた
のどれでしょう？

(0)本当に何も設定していない、で (b) のところに出てきたと予想。

追記： ごめん、タイムテーブル一切無しの方に気がまわりきっていなかった。
これだと、アシスタントでダイヤ作るの難しくなりますね。
急いで対応してみます。差し替えにする予定。

[kanedai]

予想通りの
(0)本当に何も設定していない、で (b) のところに出てきました。

アシスタントで作ろうとしたら出てきましたｗｗ

[wackdone]

TTT-043、TTT-043bからの差し替えです。何度もお手数をおかけしてすみません。

TTT-043c パッチです。バイナリは↓
  http://ux.getuploader.com/wackdone_simutrans/download/23/simuwin-wackdone-120719c.zip

アシスタントが台無しになるバグだったので修正します。
kendaiさん、素早いご指摘本当にありがとうございました。

TTT-042からの変更点：
  バグ修正： 時刻表での更新時の異常の修正、自動再設定時の範囲外値の取り扱いを改善
  機能追加： 時刻表修正時にチェックを多くした (更新しようとしたら路線のスケジュールが他で変更されていた場合の検出なども)
  仕様変更： 中継点(waypoint)に計画時間を設定した場合に評価されるようにした (前駅発時刻が更新される)
  仕様変更： 上と合わせて、計画時間の設定の無い駅、中継点ではTTT処理が一切行われない(前駅発時刻の更新もなし)
  機能改善： 複数の路線を表示させた場合に少しだけ表示が見易くなるようにした (優等マージは前と変わらずできている)

特に「仕様変更」の部分が重要かと思います。
今回の修正で、「一部だけ計画区間時間値を入れた運行」が可能になりました。
ある駅に計画時間を入れると、前の計画時間が入っている駅からその駅までが、指定された計画時間の制御対象になります。

(まぎらわしいので、TTT-043、TTT-043bの投稿は削除しました。)

[kanedai]

さっそくの反応ありがとうございます。
治ってました。

あと、前のよりもスムーズになった気がします。

[gonyo]

いろいろ試していますがよくわからない機能が多いので解説なんてとてもできません。

今普通＋急行の等間隔運行に成功しました。

気になったこと
段落ち問題の特効薬
入線振り分け信号で段落ちが直ったようです。！　大発見？（４編成2ホームで実証）　団落ちなおす実験してたつもりじゃないんですけどね。
普通同士の退避が行われて列車の順序を自動で正しく並べ変えます。　特効薬ですね
医者が患者に治療されるような状態ですが・・・　　線路構造がいかに大事かということだと思います。　そしてTTTが完璧なものになったとき入線振り分け信号は役目を終えるんでしょうね。


もう１つ：　私はいつも車庫に１編成残して運行しています。　増発したいときにそうすると便利なのです。
で、今回車庫で眠ってるものに時刻表が割り当てられちゃいました。　これで運行間隔がずれてしまった模様
　他にも車庫に１編成待機させてる人いないでしょうかね？　

他に　simutransは乱開発する人多いのでダイヤあんまり考えてられないことが多いかもしれません。

急行と普通を運行する場合　列車間隔は統一しないといけません（これがうまくできない）　　普通１２分間隔　急行13分間隔とかだと困ります。
これをあわせるには編成数を計算で求める必要があります。　必要な編成数をTTTが指示する必要がある　（普通と急行の編成数を合わせてもダメ）　編成数が多すぎると始発駅手前で渋滞する。
また増発や路線の延伸などの際設定しやすいようしておいてほしいです。

↓は成功したもののセーブデータです。

[yoyo]

043c にて
   適当に３つくらい駅を作って１つ路線を作って列車を走らせます。(tttに関する設定はしなくてもよい。)
   その後、時刻表を表示してautorefreshをONにします。
   そして列車の「車庫へ」を押すと、時刻表に車庫の座標と他の駅が追加され、
   車庫に入った瞬間にminivec_tpl<T>:[]で落ちます。
   こちらでは１００％で再現してます。

OVERRIDEについて
   overrideとfinalはvirtualメンバ関数のみが正解らしいです。
   この辺 -> http://stackoverflow.com/questions/5530022/override-non-virtual-functions-in-c-2011
   次期C++1yではnon-virtualもOKになるかも知れませんが、今のところダメみたい。
   gccが先取りしすぎなんですね。

uint32_tについて
   VC++2010にもありますが、ヘッダをインクルードしないと使えません。<cstdint> or <stdint.h> C99
   gccでも同じはずなのですが．．．

bits_per_dayについて
   ＞TTTで見える姿だけ変える感じですかね。
   そうです。

[wackdone]

皆様、動作確認ありがとうございます。
私事としては8月ががっつりどっぷりの仕事になりそうで、その前にある程度固めておきたいと考えています。
というわけで原則として問題(クラッシュするようなバグ、運行の致命的な不調など)対応優先。
機能追加は後回しですいきます。 (といっても、時刻表の見てくれを改善していくくらいしか今はアイディア無いんですけどね)

kendaiさん：深夜に何度もチェックしてくださりありがとうございます。
改版する途中で、重そうだ無駄そうだと判断した場所はちょくちょく書き直しているのですが、そんなに一気にスムーズになるような変更はしていないつもりです。
もしかして、どこかにお化け(コード内で不正に他所を破壊しているところなど) がいて、どこか直した時にその除霊ができたのかもしれません。

gonyoさん：high-low mixの振り分け成功おめでとうございます。私も嬉しい！
たしかに、choose signal を使えば入線可能ホームの数まではreorderを吸収できますね。
またconvoy reorder の原因に車庫内の列車の存在が絡んでいるというのはあり得ますね。
(すみません、reorderとは「順序の入れ替わり」。一般的な英単語かもしれませんが、コンピュータネットワークの世界では、packet reordering という風に使っていたります。
コンピュータネットワークの用語の方が使い慣れているのでつい使ってしまいますが許 して。)

現状の順序付け(というか順序付け*られ*)について簡単にさらっておくと、
  (1) (TTTを入れる前) そのままそこで走っている状態
  (2) 運行アシスタントまで行って、「始点発時刻を設定する」で時刻表の始発駅が決まるところ (で「時刻表を改定」をする必要あり)：
        この段階で、路線の全編成の位置を把握しなおして、始点駅に一番近い列車から順に、n*P+Sの時間をふっていきます。(一つの列車につき、n が1ずつ増えていく。)
  (3) 「自動調整」(一発あるいは「常に」のどちらでも) によって、始点に到着するたびに始点発時刻の変更が行われる。
        なので、ここでまた順序に合った時間が振りなおされるはず。

さて、こう書いたのはあくまで、こういう動きをする*つもり*のプログラムを書いたというだけで、バグあるいは想定できていなかった要素がどこかにあるということになります。

まず想定できていなかった要素(1)： 車庫にいる編成にどういう値を振るかは考えていなかった。(車庫にいるということの検出すらしてなかった)

あとは(2)にバグがある可能性かなぁ。バグとは言い切れないけど、(2)の段階で時刻をふって行く時に
最初のnをどうするかは課題です。今は「最も始点に近い」列車が「始点に到着する予想時刻」(計画時間から求める)をもとに、適切な n を出しています。この予想がうまくないと、まずい。
(ただこれだけでは reorder の原因には直接はならない)

また自分で試していて発生したのは(3)で、列車のスケジュールに(少しでも)無理があった場合ですかね。
無理があった時に(3)がきついのは、段落ちしちゃった値をそのまま設定されてしまうこと。

こうして見ると、「区間時間計画だけの運行」というシンプルさから「周期と発時刻」を設定した途端に始まるややこしさの間の開きが大きすぎますね。
gonyoさん式のシンプル周期運行も含めて、の間の開きを埋めるものが無いとちょっときつそう。

散文ですみませんが、とりあえず頭の中を吐き出しておきます。一回投稿。

[wackdone]

yoyoさん、ありがとうございます。

* 車庫送りにすると minivec_tplのfatalで落ちる
たしかに車庫行きの状態の扱いが微妙でした。まず落ちないようにはします。
でここで、仕様としての検討課題が。車庫送りにした編成は時刻表の上ではどう扱うべきでしょうか。
(ちなみにSimutransの内部の作りとしては、車庫送りにした途端に独自のスケジュールを持って、路線から一時的に外れてしまいます。)
  a. 時刻表の上から消す
  b. 車庫行きのスケジュールをそのまま見せてしまう (路線から一時的に外れていることをどう示すかはまた別の課題)
  c. 車庫行きなど何も知らないかのように、いつも通りのダイヤを見せるけど、マーカだけ表示されなくなる
aが一番簡単。実はcが最も難しい。とりあえずは落ちないようにaにふろうかとは思いますが。

* override
すみません、C++脳がStroustrup初版で止まっている人間なものでついていけてませんでした。ご教授ありがとうございます。やっぱり仕様は読むべきものですね。
しっかし半端な仕様作りましたね。ここ10年くらいは誰がやってるんだろう。
virtualのoverrideもremarkするべき要素はいっぱいあるけど、実はnon-virtualのoverrideの方がよりremarking必要ですよね？
どうせcastであれだけキーワード増やしちゃったのだから、overrideも non-virtual と virtual それぞれに作ってしまえばいいだろうに。
さらに implements (純粋抽象の仮想メソッドを実装する時にだけ指定する、ってJavaのまねですね) まであれば完璧ｗ

* uint32_t
ああ、ごめんなさい。stdint.hにまとまったんでしたね。たしかにインクルードしてません。
(UNIX系の多くが、sys/types.h を stdio.h から読み込んでいるんで、simutransのどこかが読み込んでいるstdio.hでなんとなくうまくいっちゃうんですよ)
いろいろとお行儀悪いですね、私。お恥ずかしい。
いずれにしてもSimutransのお行儀的には uint32_t ではなくuint32なので、そちらにまとめます。

* 独自の時刻体系での表示
まずは時刻表で、それも表示だけで、ということであれば低リスクで実験はできそうです。
入力の部分は hh:mm:ss なりのフォーマットを入力しやすくするのが手間くいそう。
あと、これやった場合、路線ごととの運行周期との関係はどうしますかね？
まずはそういうのを無視して、えいやっと全体設定でやってみるものなのかな。
例えば：
   「この時刻表は、2400tt == 1day として表示する」とどこかで設定できるようにして、
   「時刻表示形式の変更」とかいうボタンをお押すと、全部の表示が hh:mm.(ss) 形式になる
という感じ。
問題は、半端なtt==1day とされた場合に、誤差を気にするかどうかですね。
なんせ、24や60で割ることになりますので。
なんとか「ややこしい設定が少なく」「見て意味のある」(イメージしやすくなる) ようにしたいのですが。
もう一段、アイディアを集めたく思います。

とり急ぎ。
バグ修正はいましばらくお待ちください。