Java アクション数を算出するプログラムを書きたい

Question

###前提・実現したいこと
現在Javaの学習の一環で戦車を作成しています
そのなかで戦車のアクション数の算出を行うプログラムを書きたいと思っています

まず最初に以下が戦車の大まかな仕様です。必要なさそうな部分はのせていません。

移動

90度単位で方向転換できる(45度とかで止めることはできない)
90度方向転換する度に4リットルの燃料を消費する
前進と後退が可能
100m 進む度に4リットルの燃料を消費する(進むのは100m単位で150mで止まるということはできない)
動作させようとしてその動作に必要な最低単位の燃料が無い場合は動作しない
9リットルしかなくて 300m 前進しようとした場合、200m で停止し 8リットル消費する

砲

戦車には砲塔がついている
90度単位で360度無制限に回転することができる
90度回転する度に4リットルの燃料を消費する
戦車は砲弾を10発保持出来る
砲弾は装填されている順に発射される。発射時に選ぶことができない

下記いずれかの行動をする際に、アクション数が1加算される。

エンジン始動
本体90度方向転換、砲塔90度方向回転
100m前進 or 後進
発射
被弾
給油(※どれだけ給油しても1)

次に以下が実現したい内容です

初期戦車の100m南方に戦車ベータが配置されている。
この戦車が、東方向に X(m)、北方向に Y(m)、方位 D を向いた形で移動する際の、
最小のアクション数を算出するプログラムを記載せよ。
なお位置座標は、初期戦車の初期位置を基準とする。（X=0,Y=0）

例1：戦車ベータが東に100m（X=100）、北方向に100m（Y=100）、北向きの位置に移動するには最小アクション数は 5 となる。
（200m前進、右折、100m前進、左折）

戦車自体は出来上がっているのですがアクション数の算出が
現段階ではどのように実装すればいいのかのめどが立っていません。
正直計算の仕方もあいまいな状態で、メソッドとしてアクション数を取得するものを追加した方がいいのか、新たにclassを作成した方がいいのかもよくわかっていません。

移動したり方向転換するたびにアクション数が+1されるようにはしました。 ただ引数に目的地のx座標、y座標、向いている方角を入力して、例であれば「5」と返されるうなことをしたいです。

質問するのも初めてなので追加で必要な情報があれば教えてください。よろしくお願いします。

###試したこと
とりあえずコメントしていただいたように、目的地までの絶対値を100で割って
移動距離のアクション数を出してみました。（間違いがあれば教えてください）
しかし、次は旋回の回数をどう取得すればいいかで詰まってしまいました。
旋回の回数は1回か2回のどちらかということはわかっているのですが。
ド素人のコードですがレビューお願いします

//目的地までの最小アクション数を算出する
//destinationX,Yはそれぞれ目的地の座標
//directionは最終的に向いていたい方角です
//getPostion()は現在地を取得するメソッドです
     public int countAction(int destinationX, int destinationY, Direction direction) {
        int countAction = 0;
        int distanceX = Math.abs(destinationX - getPostionX());
        int distanceY = Math.abs(destinationY - getPostionY());
        countAction = countAction + (distanceY + distanceX) / 100;
        
        
    }

Answer 1

地形により移動できる場所が制限される迷路探索のようなものなら別ですが、ご質問の内容ですとクラスを追加する程の複雑な演算アルゴリズムは必要ないと思います。

考えかたとしては・・・

• 目標位置と現在位置の差の計算

異動すべき方向は最大でも2方向でよいですね。それ以上になると回り道をすることになるので絶対にアクション数は増えることになると思います。

• 東西、南北のいずれへ最初に移動すべきか

どちらにすべきかは初期方向、最終的な方向、東西、南北への移動距離が０以上かどうかが決まれば必然で決まります。

• 上記が決まれば必要なアクションは必然として決まる

必要なら最初に移動する方向へ向き、前進、必要なら方向を90度回転させて前進、最後に所定の方向へ向く

つまり必要なのは戦車クラスの機能を考えることではなく、「最小のアクション数を求めるアルゴリズム」を考えることだと思います。

Comments

[退会済みユーザー]

ありがとうございます！
とても参考になります！
こちらを参考に進めていきます！

[退会済みユーザー]

質問なのですが
書き始めたコードを質問欄に追記したのですが、どうしても今の私の書き方だとif文が大量になってしまいます。これは書き方や考え方が悪いのでしょうか。

[KSwordOfHaste]

考え方が悪いわけではありません。それを手際よく書くことができる論理の組み立てに慣れていないだけだと思います。
例えば正負で処理を分けなくても「絶対値」を求めてからそれを100で割れば移動アクション数は求まります。そうした工夫は「アルゴリズムを色々学ぶ」うちに身についていきますよ。

[退会済みユーザー]

なるほど！ありがとうございます！
やはりアルゴリズムを色々学ぶことは大事なのですね。

[KSwordOfHaste]

そうですね。プログラミングを学ぶ初期段階で最も大切なことはこうした基本アルゴリズムを考える力をつける点にあると思います。

[退会済みユーザー]

ありがとうございます。引き続きアドバイスいただけたら幸いです。

[KSwordOfHaste]

一応申し上げておきますと・・・
このサイトの質問は「端的に疑問点を示し」「端的な回答でクローズする」のがマナーです。自分が作り上げたいプログラムが完成するまで継続的に指導してもらえる場だと勘違いしないでください。
質問の内容を変更するのは「情報が不足していた」「情報が間違っていた」場合に限定したほうがよいと思います。

ま、しかし堅いことをいわずに、修正後のコードについてコメントしてみますと、「概ねよい」のではないでしょうか？ただし、問題の条件によっては「間違い」となる可能性を秘めていると自分は思います。
東へ50m, 北へ50m移動というような問題が対象になるかならないか不明ですが、もしなったとして50mの移動でも１アクションと考えるのか合計で100ｍ移動なら方向を変えても１アクションと捉えるかで現在のコードの正誤は変わってくる・・・そういうふうに思いました。

[KSwordOfHaste]

言い忘れました。「概ねよい」というのは「移動距離に関しては」です。方向転換やエンジンの始動などの配慮は入ってないですよね？

[退会済みユーザー]

そうなんですね！以後気を付けます。
移動は100m単位でしか行えないので東へ50m, 北へ50mということはございません。
方向転換やエンジン始動は配慮していません。

[KSwordOfHaste]

なるほど、そういうことならこのコードでよさそうですね。

[退会済みユーザー]

あ、すいません。エンジンに関しては考慮しませんが、燃料に関しては考慮する必要があるかもしれません。
燃料タンクに入る燃料が最大500ℓなのですがそれ以上の燃料が必要な場所に移動するときなど…

Answer 2

何もアクション回数を式一本で求める必要はないので、順次移動させて見ればいいだけのことです。

まず基本的な話ですが、X軸方向に動く際にはY座標は動かず、Y軸方向に動く際もX座標は動きません。
したがって、移動先のX座標、Y座標が決まれば、X軸方向、Y軸方向それぞれの移動回数は自ずと決まります。

であれば、アクション数を最小にするには旋回の回数を最小にすればいいことになります。

• 今向いている向きに動く必要があれば、その方向に動く。

その必要があるのに旋回する場合、例えばX軸方向の北に動く必要があるのにY軸方向である東西方向に旋回すると、いずれまた北に向かうために旋回する必要が生まれ、旋回回数が多くなる。

• 今向いている向きに移動する必要がなくなり、別方向に移動する必要があれば旋回する
• 最終的な向きがこの移動方向に沿う向きであれば、その向きを向いて移動する

北に動いた後西に動き、最終的な向きを東にするのであれば、東を向いて後退すればいい。

• そうでない場合はどちらを向いても変わらない

こういう行動をしていけば、自ずとアクション数は決まるはずです。

Comments

[退会済みユーザー]

ありがとうございます！参考になります。

Answer 3

ちょっと仕様について質問。砲塔や砲弾の仕様がありますが、計算するのは移動だけで良いのでしょうか?
戦車をオブジェクトとして表現する云々といいたいところですが、障害物の無い移動だけなら単純にベクトルの足し算の問題に落ちます(回転してから移動するのも移動してから回転するのも変わらないし、仕様上順序性のコストは無いようなのでいつ給油しても同じだから)。

Comments

[退会済みユーザー]

コメントありがとうございます。はい。今回は移動だけの計算で大丈夫です。
その後砲塔や砲弾の方も考えていこうと思っています

[kurokoba]

基本的に碁盤の目の上しか移動しない話ですよね(行き先が99m先とか100mステップで移動できないことは考えない?)。
あと計算順序に依存するかもしれない場所がありました。「方位 D を向いた形で移動する」って到着したときのむきでしょうか?
※であれば初期値として「いま戦車がむいている方向」が必要。
ちょっと仕事するので考え方だけ。

まず数学の問題として以下を把握しておく(証明できる?)ことが必要。
1.アクション数は回転・移動の順序に依存しない。
そして
2.直線で移動できる場合、直線移動が最少アクション
これは自明だと思います。回転を考えなくてよいので1パターンしかない。
これにあてはまらない場合ですが、次のことが言えます。
3.どのような経路を通るとしても移動距離が短い方がアクション数が少ない(最短経路のうちいずれかが最少アクションの候補になる)。
4.最短経路のうち、四角の辺の上をとおる2つ(右回り、左回り)のうち初期の向きから回転数が少なくなる方が最少アクション
※最短経路についてはこんな数学といたことがあるならイメージ付きやすいかも。
https://studysapuri.jp/contents/high/article/subject/math00024.html

[退会済みユーザー]

コメントありがとうございます。
「方位 D を向いた形で移動する」って到着したときのむきでしょうか?　はい。その通りです。今戦車が向いている方向を取得するメソッドもあります。

見ようと思ったらURL先が存在しませんと出てしまいました。

[kurokoba]

どうもすみません、碁盤の目の絵がでてれば何でもよかったのですが。
http://mathtrain.jp/dp

[退会済みユーザー]

ありがとうございます！

[kurokoba]

「旋回の回数」は自身を原点にとって、今戦車がむいている方向を「北」にした座標にとれば(座標の取り方なので実際の北でなくてもいい)目的の位置によって最大8パターン考えれば良いのでは?
目的地が
1北にある(回転しない)→0回
2北東にある(左右の向きだけ変える)→1回
3東にある→1回
4南東にある→2回
...。
きれいに計算する方法もあるがたかだか8なのでなんとかなる。
とりあえず書いてみれば法則も見つかる。

Answer 4

こんな感じで、どうでしょう。

戦車クラス：アクションのカウント（実装済み）、アクションのリセット、アクションカウントの取得
戦車を操作するクラス：戦車クラスへの操作。アクションカウントの取得の呼び出し

で、戦車を操作するクラスが、最小アクションを求めるようなプログラムになれば良いと思いますが、
回答になってます？

それとも、最小アクションを求めるアルゴリズムが思いつかないってことでしょうか？

追記：
旋回については、一番単純なケースから考えていくといいです。

1. 移動がまったく必要ない場合、最後の向きと現在の向きについて検討すれば良いです。

同じ方向なら、０回、真反対なら２回、９０度、２７０度の時は１回です。

1. １方向(X軸またはY軸)に移動が必要な場合

移動前に旋回が必要な場合、1回。そうでないなら１のケースと同じ。

3.　２方向に移動が必要な場合
移動だけに関していえば、１回でいいです。
なので、最初の向きが正面または、真反対のときに、追加で１回

８方向に移動することを整理すると

• 移動先が正面、または真背面の場合（２通）

　0回、1回、2回のどれか

• 真横の場合（２通）

　0回、1回のどちらか。に、移動前の旋回が１回追加

• ナナメの場合（４通）

　0回、1回のどちらか。に、移動中の旋回が１回追加

とりあえず書いてみれば法則も見つかる。

見つかりましたよね？

Comments

[退会済みユーザー]

コメントありがとうございます！
はい。アルゴリズムが思いつかないという意味でした。

[momon-ga]

前進、後進に違いがないので、X、Y座標の移動（100単位）と、エンジン始動、旋回（１回でOK）
と、その移動にかかる給油回数、もとめればよいかと。（kurokobaさんの言うとおり）
給油するのにエンジン止める必要あれば、エンジン始動も追加ですね。

[退会済みユーザー]

ありがとうございます！
参考にして進めてみます！

[退会済みユーザー]

すいません。質問です
コメントに旋回（1回でOK）と書いてあるのですが、旋回が2回必要になることはありませんか？

[momon-ga]

KSwordOfHasteさんの回答にもありますが、障害物がない前提ならば、
「移動すべき方向は最大でも2方向」になります。

最初の自分の向きが北（南）なら、Y方向の目標に移動します。
次に、旋回を１回すれば、X方向に移動できます。

おっと、移動のみを考慮してます。もし砲塔の向きを考慮する必要あるなら、旋回が２回になることもありえます。（とはいえ、X、Y座標のどちらががそろっていて、かつ後ろ向きの場合だけですかね）

[退会済みユーザー]

ありがとうございます！
x方向に移動したのちに最後に向いている方角を北に指定した場合もう一度旋回が必要にならないでしょうか。
よろしくお願いします

[momon-ga]

なるほど、問題見落としてました。最後に「方位 D を向いた形」というのがあるのですね。
おっしゃる通りです。

[退会済みユーザー]

確認ありがとうございます！
いえ、私がながながと見にくい質問を書いてしまったので。

[退会済みユーザー]

追記ありがとうございます！
とりあえず手を動かして書いてみることが大事なんですね！

[momon-ga]

ちなみにナナメの移動って、実質、真横移動の前に前進（後進）があるだけで、検討するのは２パターンだけですね。