斜めの経路の出し方

「お前はなんでドメイン持っていて、ブログをすでに2回書いた形跡があるんだよ。」と思われるでしょう。今後ちゃんとブログを書きます。書いていなかったら煽ってください。昔にやりたいことがあってドメイン取得したけど結局何もしてないので、ドメインの保守にとても無駄なコストがかかっております。

というわけで、この記事は2024年のWMMC Advent Calendarの１日目の記事です。

WMMC Advent Calendar 2024 - Adventar

【私たちについて】我々は早稲田大学マイクロマウスクラブ(WMMC)です。個々人がマイクロマウス競技を行なっています。以後お見知りおきを！【概要】さて、今年もはじまりました WMMC Advent calendar！！！毎日誰かがブログを書いていきます。内容は不問！WMMCメンバー・OBOGのみなさんはマイ...

なかなか枠が埋まる気配がないのですが、みなさん書いてくださいよ！！って言いたいですが学生大会忙しすぎて1日中の投稿ができず、日付が変わって2日になっております。ごめんなさい🙇‍♂️🙏

今回は、自分の斜めの経路の出し方を書き残しておこうと思います。斜め最短走ったことない人の話なので、話半分で読んでください。

ダイクストラ法とは（説明は他所に任せる）
ノードの配置方法
最後に

ダイクストラ法とは（説明は他所に任せる）

私は斜めの経路の導出には、歩数マップを作成後、ダイクストラ法と呼ばれる探索アルゴリズムを使用しています。探索走行は足立法です。

ダイクストラ法ってなんだ！！という人は、ダイクストラ法の詳しい解説は以下のリンク群を参考にしてください。

https://www.youtube.com/watch?v=X1AsMlJdiok（大学1、２年の時にお世話になった人が多いだろうヨビノリさんの動画です）
http://www.deqnotes.net/acmicpc/dijkstra/

ダイクストラ法では、隣接するノード同士のコスト合算値の比較を繰り返すことで、コストが最小となる経路を導出することができます。確実にコストが最小となる経路が導出できるので素晴らしいアルゴリズムです。

ノードの配置方法

直進と超信地orスラロームで一区画ずつ進む走行で最短経路を導出する際は、区画中心から東西南北の方向に歩数を計算していると思います。この方法で斜めの導出を行うと、壁の情報を参照しつつ、進行パターンを分けなければならないので膨大な場合分けをする必要があります。

場合分けの数は多いほど、場合分け漏らしが発生しバグの原因となります。膨大な場合分けによるバグを避けるためにも、斜めに走行するためには区画の辺の中心から進行方向を考えると分かりやすくなります。図で表すと以下の通りです。図のようにノードを配置することで斜め方向の経路を考えやすくなります。人によっては区画の中心にもノードを配置しているらしいのですが、必要なのでしょうか。

私は以下のようにノードの番号を割り振っています。迷路周囲の確定壁の位置にはノード番号を割り振らず、全480個のノードでダイクストラ法を行っています。

歩数を比較していき、確定した進行方向のノードの番号が現在ノードの番号から+16で斜め、+31で直進…と経路を導出していきます。私のスパゲッティコードの一部を切り取って、経路のデバッグの関数をここに書いて場合分けを示しておきます。ノードを進むごとに現在向いている方向を更新しており、向いている方向に応じて「右斜に進んだ」「そのまま直進」…の場合分けをしています。例えば、北を向いた状態で次のノードが+16の場合は、右斜に進み、マウスの進行方向は北東になります。

// 方向を取得する関数
string debugGetDirection(int16_t from, int16_t to, uint8_t direction, uint8_t pre_route) {
   if(direction == North){
        if (to - from == 31) {
            return "直進";
        }else if (to - from == 16) {
            return "右斜進";
        }else if (to - from == 15) {
            return "左斜進";
        }else {
            return "不明";
        }
    }
    else if(direction == East){
        if (to - from == 1) {
            return "直進";
        }else if (to - from == -15 ) {
            return "右斜進";
        }else if (to - from == 16) {
            return "左斜進";
        }else {
            return "不明";
        }
    }
    else if(direction == West){
        if (to - from == -1) {
            return "直進";
        }else if (to - from == 15) {
            return "右斜進";
        }else if (to - from == -16) {
            return "左斜進";
        }else {
            return "不明";
        }
    }
    else if(direction == South){
        if (to - from == -31) {
            return "直進";
        }else if (to - from == -16) {
            return "右斜進";
        }else if (to - from == -15) {
            return "左斜進";
        }else {
            return "不明";
        }
    }
    else if(direction == NorthEast){
        if (to - from == 16) {
            return "斜進";
        }else if (to - from == -15) {
            return "右斜進";
        }else if (to - from == 15) {
            return "左斜進";
        }else if (to - from == 1 || to - from == 31) {
            return "直進";
        }else {
            return "不明";
        }
    }
    else if(direction == SouthEast){
        if (to - from == -15) {
            return "斜進";
        }else if (to - from == -16) {
            return "右斜進";
        }else if (to - from == 16) {
            return "左斜進";
        }else if (to - from == 1 || to - from == -31) {
            return "直進";
        }else {
            return "不明";
        }
    }
    else if(direction == SouthWest){
        if (to - from == -16) {
            return "斜進";
        }else if (to - from == 15) {
            return "右斜進";
        }else if (to - from == -15) {
            return "左斜進";
        }else if (to - from == -1 || to - from == -31) {
            return "直進";
        }else {
            return "不明";
        }
    }
    else if(direction == NorthWest){
        if (to - from == 15) {
            return "斜進";
        }else if (to - from == 16) {
            return "右斜進";
        }else if (to - from == -16) {
            return "左斜進";
        }else if (to - from == -1 || to - from == 31) {
            return "直進";
        }else {
            return "不明";
        }
    }
    else return "不明";
}

以上の場合分けを済ませると、https://www.kerislab.jp/posts/2017-09-03-pattern-of-turn/にある最短走行パターンを導き出すことができます。（KERIさんのブログはとてもとても参考になるので、ブックマークしておきましょう）

最短走行パターンの中で、直線から入るターンは

最短180°
最短135°
最短90°
最短45°

斜めから入るターンは

最短45°
最短135°
最短斜め90°

と直進からのターンなのか、斜めからのターンなのかで大きく分類できます。上で示したコードの場合分けの結果を活用するとすべての経路をターンに置き換えることができます。例えば、「直進→左斜進→斜進」の場合は直進から斜め方向へターンする左方向に旋回する最短45°とわかります。他のターンの置き換えの場合分けは自分でやってみましょう。

今回示した方法の注意点として、スタートノード（上の図では15番のノード）はスタート区画の上の辺からスタートしていて、導出される経路にスタートの区画を走る分の直線がないので、開幕ターンはスタートの直線を考慮した例外処理が必要となります。