最短距離までの道を表示

[馬鹿]

スタートとゴールを入力したら
ゴールまでの最短距離を調べて、その行き方を表示するプログラムを作りたいんですがわかりません。
上下右左の四方向に進むプログラムはわかったんですが、右上、左上、右、左、右下、左下の六方向に進むプログラムが作れません。
ご教授お願いします。

#include <stdio.h>
int main(void)
{
int startx,starty,goalx,goaly;
int x,y,a,b;
printf("スタートx:");
scanf("%d",&startx);
printf("スタートy:");
scanf("%d",&starty);
printf("ゴールx:");
scanf("%d",&goalx);
printf("ゴールｙ:");
scanf("%d",&goaly);

x=goalx-startx;
y=goaly-starty;
for(a=1;a<=x;a++)
{
if(x>0)
printf("右");
else if(x<0)
printf("左");
}

for(b=1;b<=y;b++)
{
if(y>0)
printf("下");
else if(y<0)
printf("上");
}
return (0);
}

[パコネコ]

このプログラム、上もしくは左に行くの？
右と下しか表示されませんでした。
左のときと下のときはfor文の条件に当てはまらないからループしませんよ…
まずはそれからな気がします。

[box]

盤面の定義はどこにあるのですか？

[パコネコ]

こんなのどうですか？
壁の設定がないならですけど…
x=startx;
y=starty;
while(goalx!=x || goaly!=y){
if(x<goalx){
printf("右");
x++;
}else
if(goalx<x){
printf("左");
x--;
}
if(goaly<y){
printf("下");
y--;
}else
if(y<goaly){
printf("上");
y++;
}
printf("\n");
}
左下を(1,1)とした場合ですけど…

[馬鹿]

うぅ
すいません
盤面の定義は
左がｘ軸で右がｙ軸で

0,0 1,0 2,0 3,0 4,0

0,1 1,1 2,1 3,1 4,1

0,2 1,2 2,2 3,2 4,2 ・・・
・
・
・

という続いてく四角い盤上です

＞このプログラム、上もしくは左に行くの？
すいません一回だけ調べて完成した気になってました

[フリオ]

　つまり、

　xy平面上(x >= 0、y >= 0)の格子点から任意の2点を選んでstart、goalとし、
その2点間の最短ルートを上、下を除いた6方向を使って表せ。
　
ということでいいのでしょうか？

　また、そうなら、
全ての最短ルートを表示するのでしょうか、それとも、そのうちの1つを表示すればいいのでしょうか。
　

[馬鹿]

はい！そのとおりです！

最短ルートは一つでいいです

[パコネコ]

上と下を除いた6方向の時点で最短移動ではないですけどね…
そういう仕様なんでしょうけど、たとえばスタートとゴールのx軸の距離（絶対値？）とy軸の距離でy軸の距離のほうが大きい場合、一旦ゴールを通り抜けて戻るという作業（ジグザグに縦に進む）を行って、
ゴールを目指すことになりますよね…

[kazuoni]

一番重要な点が明確になってないのですが、障害物はあるのでしょうか？
障害物があるとないとはかなり難易度か変わってきます。

1) 障害物がある場合
敵対探索が必要になります。簡単な探査としてはA*(エースター)探索ですかね。
全探索ではないので手軽です。が、パラメータの設定によって精度がかなり変わってきます。

2) 障害物がない場合
まずどこがスタートでどこがゴールでもスタートが左上、ゴールが右下で対角をなす四角形（※1）で考えると楽です。
レスに書いてあった座標系（第4事象）で考えると、

1,右斜め下に進む
↓
2,四角形（※1）の辺に当たる
↓
3,
x軸と水平な辺：あとはx軸+方向に進むだけ
y軸と水平な辺：一度左斜め下に進み、1に戻る
両方：ゴール

で最短になるかと思います。


おそらく課題は2)のような気がしますが、暇だったんで1)を作ってみました。
DOSからどうぞ。
以下の参考サイトをもろパクリ参考にしました。
正直うまく動いてるのかはわかりませんｗ

銀のがまぐち亭　A*経路探索
ttp://gingama.hp.infoseek.co.jp/java/a_star.html

#全探索って・・・面倒くさそう。

[馬鹿]

ありがとうございます!
本当に助かりました！！

[フリオ]

　解決してますが、考えてみました。
これでいい...はず。
　

#include <stdio.h>
#include <math.h>

typedef struct point{
    int x, y;
} point;

typedef struct step{
    int x, y;
} step;

typedef struct dist{
    int x, y;
} dist;

int main(void)
{
    point p1, p2;
    dist d;
    step s;
    
    fputs("Start < ", stdout);
    scanf("%d %d", &p1.x, &p1.y);
    fputs(" Goal < ", stdout);
    scanf("%d %d", &p2.x, &p2.y);
    d.x = labs(p1.x - p2.x);
    d.y = labs(p1.y - p2.y);
    printf("\n(%d, %d)", p1.x, p1.y);
    for(s.x = 1, s.y = p1.y > p2.y ? -1 : 1;d.y > 1 && d.y > d.x; d.y -= 2){
        printf("->(%d, %d)", p1.x += s.x, p1.y += s.y);
        printf("->(%d, %d)", p1.x -= s.x, p1.y += s.y);
    }
    for(s.x = p1.x > p2.x ? -1 : 1; p1.y != p2.y; ){
        printf("->(%d, %d)", p1.x += s.x, p1.y += s.y);
    }
    for(s.x = p1.x < p2.x ? 1 : -1; p1.x != p2.x; ){
        printf("->(%d, %d)", p1.x += s.x, p1.y);
    }
    putchar('\n');
    return 0; 
}