- ベストアンサー
迷路生成についての質問
- 迷路生成についての質問
- 迷路生成の方法について教えてください
- 迷路生成のアルゴリズムに関して詳細を教えてください
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (1)
- はなおか じった（@Jitta）
- ベストアンサー率42% (69/161)
前回の、本当に解が求まりました？「ゴールまで行けるか？」を出すだけなら、あれでもいいのでしょうが。 今回のですが、まず、設計しましょうよ。設計したら、コメントで「何をする」というのを埋めましょう。すると、ソースを組み立てながらでも、「しなければいけないこと」を見失わずにすみます。 それで、奇数偶数ということですが、１つずつ進んでいくとですね、、、 □道 ■壁 ■□■■■ ■□□■■ ■□□□■ ■■■□■ ってことにもなりますよ(^^; これの予防策も考えなければなりません。「２つ進む」というのは、１つの予防策なんですね。だから、本当に奇数も偶数も対応しなければならないのか、というところを、もう一度考え直すべき、と思います。 それから、迷路の座標ですが、 typedef struct POINT { int x; int y; } Point; typedef enum MAZEWALL { NODEF = -1, ROAD = 0, WALL = 1 } MazeWall; typedef struct MAZE { Point size; Point start; Point goal; MazeWall wall[width_max][height_max]; } Maze; かなぁ？ ＃＃＃＃＃ やっぱり、２０年近く前に作ったプログラムは、きれいさっぱり忘れてるなぁ(^^; もし残っていても、５インチフロッピーだし。。。
お礼
御礼が遅くなり申し訳ありませんでした。 前回のは解があることが確かめられる事が 最低限の条件だったので良しとしました。 最短経路を求めるというは解があることが分っているならば もとめる事ができるやつを作りました。 私が作った迷路生成のやつは奇数×奇数しかできないんですよね。 期限があったので仕方なく 乱数を一つ得るごとに解探索するという方法を とりました。 出来上がりは見事に迷路っぽくありません。 迷路に関するアルゴリズムについて集中的に 書いてある本でも有ればよいのですが見つからず 残念です。 この夏休みの間に達成したいと思います。 ほんとに何度も何度もご迷惑をおかけして 申し訳ありませんでした。
関連するQ&A
- 迷路を解くプログラムについて
迷路を脱出する経路を探索するプログラムを作成したいのですが、 何をすればいいのかまったくわかりません 以下のプログラムはあるんですが、このプログラムを改良していくということなんでしょうか？左上からスタートして右下がゴールらしいのですがやり方教えてください #include <stdlib.h> #include <stdio.h> #include "List.h" #define LEN 256 int maze[LEN][LEN]; void readMaze(char* filename, int *w, int *h, int maze[LEN][LEN]) { FILE *fp; int x, y; if (0 != fopen_s(&fp, filename, "r")) { fprintf(stderr, "指定された迷路の入力ファイルを開くことができませんでした．\n"); exit(-1); } fscanf_s(fp, "%d,%d\n", w, h); for (y = 0; y < 2 * *h + 1; y++) { for (x = 0; x < 2 * *w + 1; x++) { fscanf_s(fp, "%d%*[^-0-9]", &(maze[y][x])); } } fclose(fp); } void writeMaze(char* filename, int w, int h, int maze[LEN][LEN]) { FILE *fp; int x, y; if (0 != fopen_s(&fp, filename, "w")) { fprintf(stderr, "指定された迷路の出力ファイルを開くことができませんでした．\n"); exit(-1); } fprintf_s(fp, "%d,%d\n", w, h); for (y = 0; y < 2 * h + 1; y++) { for (x = 0; x < 2 * w + 1; x++) { fprintf_s(fp, "%d", maze[y][x]); if (x < 2 * w) { fprintf_s(fp, ","); } else { fprintf_s(fp, "\n"); } } } fclose(fp); } // シンプルなバージョン：なるべく右下へ行けるなら右下へ int main(int argc, char** argv) { int w, h; int x, y; if (argc < 3) { fprintf(stderr, "迷路の入出力ファイル名を指定してください．\n"); exit(-1); } // 迷路読込 readMaze(argv[1], &w, &h, maze); // maze[1][1] から maze[2*h-1][2*w-1] までのルートを探す x = 1; //座標の初期化 y = 1; while (x != 2 * w - 1 || y != 2 * h - 1){ if (maze[y][x + 1] == 0) { // 右にまだ行ってない？ maze[y][x] = 1000; x = x + 1; } else if (maze[y + 1][x] == 0) { // 下にまだ行ってない？ maze[y][x] = 1000; y = y + 1; } else if (maze[y][x - 1] == 0) { // 左にまだ行ってない？ maze[y][x] = 1000; x = x - 1; } else if (maze[y - 1][x] == 0) { // 上にまだ行ってない？ maze[y][x] = 1000; y = y - 1; } else if (maze[y][x + 1] == 1000) { // 行き止まりなので右に引き返す maze[y][x] = 1; x = x + 1; } else if (maze[y + 1][x] == 1000) { // 行き止まりなので下に引き返す maze[y][x] = 1; y = y + 1; } else if (maze[y][x - 1] == 1000) { // 行き止まりなので左に引き返す maze[y][x] = 1; x = x - 1; } else if (maze[y - 1][x] == 1000) { // 行き止まりなので上に引き返す maze[y][x] = 1; y = y - 1; } } maze[2 * h - 1][2 * w - 1] = 1000; // ゴール // 答えを濃い色に // 上記のプログラムはすでに答えを濃い色(1000)にしている // 迷路書出 writeMaze(argv[2], w, h, maze); return 0; }
- ベストアンサー
- C・C++・C#
- classを使って座標軸を求めるコード
やさしいJavaからの問題です。 次のように、整数値の座標をあらわす MyPoint クラスを作成してください。 フィールド private int x; (X座標) private int y; (Y座標) メソッド public void setX(int px); (X座標を設定する) public void setY(int py); (Y座標を設定する) public int getX(); (X座標を得る) public int setY(); (Y座標を得る) という問題で、回答は以下の通りですが、 class MyPoint { int x; int y; void setX(int px) { x = px; } void setY(int py) { y = py; } int getX() { return x; } int getY() { return y; } } class Sample5 { public static void main(String[] args) { MyPoint p1; p1 = new MyPoint(); p1.setX(10); p1.setY(5); int px = p1.getX(); int py = p1.getY(); System.out.println("p1のX座標は" + px + "Y座標は" + py + "でした。"); } } 教科書の関連の章ではreturnが先に来ているのですが、突然この問題ではvoidから始まっているのですが、int getX()～return y;までとvoid setX～y = py;までの部分 の順番を変えてもいいですか？
- ベストアンサー
- Java
- C言語のキューに関する質問です。
キューの演習が出たのですが全く手が出ず 困っています。 どなたか詳しい方にご助力いただけたらと思います。 以下問題です。 左上の座標を(0,0) とするマス目でできたNxNマスの迷路があり、 ’*’ は壁で、’ ’ は空きマスの通路とする。下記のサンプルを修正して、 このような迷路において、指定したスタートS からゴールG まで、 下記の手順で最短距離を求めるプログラムをつくれ。 手順1: スタート位置の座標=(sx,sy) と距離=0 をキューに記録する 手順2: キューが空になるまで以下を繰り返す。 手順2-1: キューから位置と距離を取り出し、現在の位置と距離とする。 手順2-2: もしその位置がゴールG ならば繰返しを抜ける。 手順2-3: 現在の位置の上下左右を調べ、空きマスならば(現在の距離+1) を そのマスの距離として座標とともにキューに保存する。 手順3: ゴールに到達していれば距離を出力して終了する。 • N は7 とする。 • 一度通った道を記録するように工夫することで、効率よく計算することもできる。 • G に到達できないことが分かった時は-1 を出力すること。 例えば、迷路が最大でもN x N マスしかないことを利用すると、 距離がN x N を越えてもG に辿り着けないと、 G に到達できない迷路であることが分かる。 /* (x,y) 地点とそこまでの距離c を記録する構造体*/ struct cost { int x; int y; int c; }; int main(void) { #define BUFSIZE (N*2) char buf[BUFSIZE]; char maze[N][N]; int i, j, sx, sy, gx, gy; struct cost pos; /* 迷路を読み込み、maze にセットする。*/ for (i = 0; i < N; i++) { fgets(buf, BUFSIZE, stdin); for (j = 0; j < N && (buf[j] != ’\n’ && buf[j] != ’\0’); j++) { if (buf[j] == ’S’) { sx = j; sy = i; buf[j] = ’ ’; } else if (buf[j] == ’G’) { gx = j; gy = i; buf[j] = ’ ’; } maze[i][j] = buf[j]; } while (j < N) maze[i][j++] = ’ ’; } /* ※ここを主に修正する */ /* 最短距離を表示する。*/ printf("%d\n", pos.c); return 0; おそらくキューの実装からやらなければならないのですが、 取り出すときの戻り値やら構造体、二次元配列の扱い等々で ちんぷんかんぷんです。 どうかよろしくおねがいします。
- 締切済み
- C・C++・C#
- C言語 格子点が多角形の中にあるかどうか？
こんにちは. 私はプログラミングを勉強しはじめて3ヵ月くらいです. 今、与えられた多角形（例えば、（0,0）,(3,7),(5,7),(8,3),(4,1),(1,0)の五点からなる多角形)の内部に格子点が存在するかどうかをチェックする（存在すれば1を返す等）ということをプログラミングを利用して,解決したいと思っています.最終的にはそれを利用して与えられた多角形をビットマップ表示にすることが目的です. 現在ある一つの自分の決めた点に関しては与えられた多角形を打ち込むことによって中か外かを判定する関数はできているのですが、１００×１００個の計１００００個分の格子点に関してすべて中にあるか外にあるかを判定したいのですが、なかなか上手くいきません. 分かる方いらっしゃいましたら、アドバイスやプログラムの方よろしくお願いします. 今できているプログラムをのせておきます. #include <stdio.h> #include <stdlib.h> /* #define JUST_ON 2 */ #define JUST_ON 1 int insidePolygon(int x, int y, int pn, int *px, int *py); int insidePolygon(int x, int y, int pn, int *px, int *py) /* x and y are the vertex I want to know in polygon. pn is the number of vertex of polygon *px and *py are the vertex of polygon */ { int i, j; int inside; double yy; if (pn < 1) return 0; if (pn == 1) return x==px[0] && y==py[0]; /* Point (x,y) just lies on the edge or vertex of polygon */ for (i = 0, j = pn-1; i < pn; j = i++) { if (py[i] == py[j] && y == py[i] && ((px[i]<=x && x<=px[j]) || (px[j]<=x && x<=px[i]))) return JUST_ON; else if (py[i] != py[j] && ((py[i]<=y && y<=py[j]) || (py[j]<=y && y<=py[i])) && x == (double)(px[j]-px[i])*(y-py[i])/(py[j]-py[i])+px[i]) return JUST_ON; } /* Point (x,y) is inside/outside polygon */ inside = 0; yy = y + 0.5; /* shift y to avoid acrossing the poly's edges or vertices */ for (i = 0, j = pn-1; i < pn; j = i++) { if (((py[i]<=y && y<py[j]) || (py[j]<=y && y<py[i])) && x < (double)(px[j]-px[i])*(yy-py[i])/(py[j]-py[i])+px[i]) inside = !inside; } return inside; } int main() { int ii; int xx, yy; int pnpn; int pxpx[100], pypy[100]; int ret; printf("Enter (x,y) of a point -> "); scanf("%d %d", &xx, &yy); printf("Enter the number of vertics of the polygons -> "); scanf("%d", &pnpn); for (ii= 0; ii < pnpn; ii++) { printf("Enter %d-th vertics's (x, y) -> ", ii+1); scanf("%d %d", &pxpx[ii], &pypy[ii]); } ret = insidePolygon(xx, yy, pnpn, pxpx, pypy); if (ret == 0) printf("The point is outside the polygon.\n"); else printf("The point is inside the polygon\n"); }
- 締切済み
- C・C++・C#
- 配列のソート
Javaのプログラムで、以下のように半径rでソートして並び替えて出力したいのですがどうやって作ればいいのでしょうか？ ご教授願います。 0x座標は0 y座標は0 半径は48 1x座標は1 y座標は2 半径は42 2x座標は2 y座標は4 半径は5 3x座標は3 y座標は6 半径は75 4x座標は4 y座標は8 半径は21 0x座標は2 y座標は4 半径は5 1x座標は4 y座標は8 半径は21 2x座標は1 y座標は2 半径は42 3x座標は0 y座標は0 半径は48 4x座標は3 y座標は6 半径は75 半径の値はランダムです 自分では以下まで作りました。なるべく以下の形は変えないようにしたいです。 class Circle{ private int x,y,r,j; private static int i=0; Circle(int px,int py,int pr) { x=px; y=py; r=pr; } public static void show(Circle c){ System.out.println(i+"x座標は"+c.x+" y座標は"+c.y+" 半径は"+c.r); i++; } public static void sort(Circle c){ } } class Sample{ public static void main(String args[]) { Circle[] a=new Circle[5]; for(int i=0;i<a.length;i++) { a[i]=new Circle(i,2*i,(int)(Math.random()*100)); a[i].show(a[i]); } } }
- 締切済み
- Java
- クラスメソッドのみのクラスのオブジェクト生成は不可？？
あるテキストのjavaの問題です。 public class Draw{ static void pixel(int x,int y){ /*座標（ｘ、ｙ）に点を描画*/ } static void line(int x1,int y1,int x2,int y2){ /*座標（ｘ１、ｙ１）～（ｘ２、ｙ２）に線を引く*/ } } で、これを実行するための以下のようなクラス public class TestDraw{ ＜ここに入力＞ } という問題なのですが2つまでは絞れたのですが、 （1） public static void main(String args[]){ Draw d = new Draw().line(10,10,20,30); } ↑× (2) public static void main(String args[]){ Draw.line(10,10,20,30); } ↑○ (2)はｌｉｎｅメソッドがstaticメソッドだからオブジェクト生成しなくても良い、ということなんですが (1)も正解のような気がするのですが・・・ 解説によると「ｌｉｎｅはｖｏｉｄなのでnew Draw().line(10,10,20,30);とすれば正解、とあります。 どうもいまいち理解できません。 クラスメソッドはオブジェクト生成しなくとも良い→オブジェクト生成できない ということなのでしょうか？ それからちなみに、public classって2つ記述できないんではありませんでしたか？
- ベストアンサー
- Java
- 特定範囲内に一部でも属す線分を抽出する方法
現在MySQLにてシステムの構築を考えていますが、 SQLの組み立てについて壁に当たったので、質問させて頂きます。 線分の座標を表す以下のようなテーブルが存在するとします。 線分テーブル「tblLine」 項目： 開始X座標[SX], 開始Y座標[SY], 終了X座標[EX], 終了Y座標[EY] このテーブルから任意の座標点(PX,PY)に 近い線分を抽出しようと考えております。 具体的には、上記座標点のX座標、Y座標を プラスマイナス10して出来る以下の4点 (PX-10,PY-10) (PX+10,PY-10) (PX-10,PY+10) (PX+10,PY+10) からなる四角形に、線分の一部でも属すものを すべて抽出できればと考えています。 線分の一部でも属すもので、考えられるパターンは (1)線分すべてが四角形に含まれる。 (2)線分の開始点or終了点のどちらかが四角形に含まれる。 (3)線分の開始点or終了点を除く一部が四角形に含まれる。 になると思います。 (1)、(2)については、開始点と終了点の座標のどちらかが PX-10～PX+10とPY-10～PY+10の条件を満たすものとして 抽出すればよい為、SQLを組み立てるのは難しくないですが、 (3)についてはどのようにSQLを組み立てればよいのかが わかりません。 ちなみに、範囲を四角形にしたのは、 SQLを簡素に、重くならないように考えてのことです。 円(点からの距離)のが簡単or速いということであれば その方法をご教授願いたいです。 ご回答、またはアドバイスをよろしくお願い致します。
- ベストアンサー
- MySQL
- 座標上のある点が、ある3つの座標点で結んだ三角形の領域内にあるか調べる
座標上のある点が、ある3つの座標点で結んだ三角形の領域内にあるか調べる方法。 座標上に3つの点(x1,y1)(x2,y2)(x3,y3)で結ばれた三角形があります。 ある点(px,py)が、この三角形の内側の領域に存在するかどうかを知りたいのですが、 数学のなんという分野で、どういう求め方をするのかがわかりません。 どなたかお力添えいただければ幸いです。 関係ないかもしれませんが、左上を0,0とし、右下はn1,n2の、 Windowsペイントのようなマイナスを考慮しない座標になっています。 線上を内側とするか、外側とするかはどちらでもかまいません。 どなたかお詳しい方、お暇なときにでもご回答よろしくお願いします。
- ベストアンサー
- 数学・算数
- C言語の課題について
何度も申し訳ありません。 http://okwave.jp/qa/q7877142.html や http://okwave.jp/qa/q7878947.html より、回答を受けてプログラムを作成しているのですが、 衝突時の時間と座標をどのように作成すれば良いか分からなく、 一秒後の点Pの位置を算出したのですが、合っているかどうかが分かりません。 非常に難しくて困っています。お助け下さい。 ソースコード #include <stdio.h> #include<math.h> int main(void) { float p,v,vx,vy,x,y,x1,y1,katamuki,gyaku,seiki_x,seiki_y,n,touei_x,touei_y,idoux,idouy,px,py; x=1.0; y=1.0; vx=1.0; //x方向の速さ vy=-2.0; //y方向の速さ y1=(1/y); //逆数 x1=(1/x); //逆数 seiki_x=x1/(sqrt(x1*x1+y1*y1)); seiki_y=y1/(sqrt(x1*x1+y1*y1)); n=-(vx*seiki_x)+(vy*seiki_y); //nは内積 touei_x=n*seiki_x; //touei_xは投影x軸 touei_y=n*seiki_y; //touei_yは投影y軸 idoux=vx+2*touei_x; //衝突後、点Pのxの移動方向 idouy=vy+2*touei_y; //衝突後、点Pのyの移動方向 px=-idoux; //点Pのx座標 py=-idouy; //点Pのy座標 printf("1秒後の位置は点P(x,y)=(%f,%f)",px,py); return 0; } 出力結果 1秒後の位置は点P(x,y)=(2.000000,5.000000) 何かおかしなところがあれば追加や修正等をしてくれれば幸いです。
- ベストアンサー
- その他（学問・教育）
- C言語なうなんですが、コンパイルまでは行ったんですが、セグメントエラー
C言語なうなんですが、コンパイルまでは行ったんですが、セグメントエラーを起こしてしまいます。初心者なのでどこがおかしいのかもわかりませんので、ご指摘いただけるとありがたいです。 以下がそれでゲソ。始点と終点を指定して線を描いてもらうプログラミングを目指す。 #include <stdio.h> #include "../Glib/Glib.h" int main(void) { int x1,y1,x2,y2; printf("直線の始点の座標（x1,y1）のx1,y1を、間にカンマ','を入れて入力してください。"); scanf("%d" ,"%d" ,&x1 ,&y1); printf("直線の終点の座標(x2,y2)のx1,y1を、間にカンマ','を入れて入力してください。"); scanf("%d" ,"%d" ,&x2 ,&y2); G_init(); G_open(800,600,"Draw Line"); G_show(); G_black(); G_fillrect(0, 0, 800, 600); G_flush(); printf("Return Key を押してください。\n"); getchar(); G_white(); G_fillrect(0, 0, 800, 600); G_rgb(0,0,8); void G_line(int x1, int y1, int x2, int y2); G_flush(); printf("Return key を何回か押すと終了します。\n"); getchar(); getchar(); G_close(); return (0); }
- ベストアンサー
- C・C++・C#
お礼
何とか作ることができました。 というかこれも奇数のサイズの迷路しか作れませんでした・・・(涙 こうなったら壁を一つ作るごとに解探索をして いくしかないのかなと思っています。 本当にご迷惑おかけしました。 有難うございました。