Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 24.02.2013, 15:58   #1
Wanz
 
Регистрация: 24.02.2013
Сообщений: 8
Вопрос Поиск пути в лабиринте. Маршрутный алгоритм. C#

Здравствуйте. Cвоих мозгов боюсь не хватит. Получил задание от препода. Необходимо написать программу поиска пути в лабиринте с помощью маршрутного алгоритма. Суть алгоритма вроде бы понял, на бумаге решал, но когда дело дошло до того что-бы начать кодить...оказался в тупике, совсем не пойму с чего мне начать. На форму накидал: кнопку и datagridview с десятью столбцами. Грид заполняю конечно криво, но ламер... что с меня взять. Я не прошу рабочих исходников, лижь дельный совет знающих людей...с чего мне начать? От чего оттолкнуться?
Код:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        
        public Form1()
        {
            InitializeComponent();
        }
        
 
        private void button1_Click(object sender, EventArgs e)
        {
            this.dataGridView1.Rows.Clear();
            this.dataGridView1.Rows.Add("3", "0", "1", "1", "1", "0", "1", "1", "1", "1");
            this.dataGridView1.Rows.Add("0", "1", "0", "0", "1", "0", "1", "1", "1", "1");
            this.dataGridView1.Rows.Add("0", "0", "1", "0", "1", "0", "1", "0", "1", "1");
            this.dataGridView1.Rows.Add("1", "1", "0", "1", "0", "0", "0", "1", "0", "1");
            this.dataGridView1.Rows.Add("0", "0", "0", "0", "1", "0", "1", "1", "1", "1");
            this.dataGridView1.Rows.Add("0", "1", "0", "0", "1", "1", "1", "0", "1", "1");
            this.dataGridView1.Rows.Add("0", "0", "0", "1", "1", "0", "0", "0", "0", "1");
            this.dataGridView1.Rows.Add("0", "0", "1", "0", "0", "1", "1", "0", "1", "0");
            this.dataGridView1.Rows.Add("1", "0", "0", "1", "1", "0", "1", "0", "1", "0");
            this.dataGridView1.Rows.Add("0", "0", "1", "0", "1", "0", "1", "1", "0", "4");
            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "0")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.White;
                    }
                    else if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "1")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Black;
                    }
                    else if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "3")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Green;
                    }
                    else if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "4")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Purple;
                    }
                   
                    
                    DataGridViewColumn column = dataGridView1.Columns[j];
                    column.Width = 25;}
                }
 
 
 
          //здесь скорее всего пытался провести конкатенацию значений "1"...не вышло
            
            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 10; j++)
 
                {  
                    object s = dataGridView1.Rows[j].Cells[j].Value;
 
                    if (s == "1")
                    { 
                      string ss =s.ToString();
                      ss += ss;
                        textBox1.Text = ss;
                    }
                    
                    
                }
            }
 
            
 
 
         
 
 
 
            }
 
        private void dataGridView1_CellContentClick(object sender, DataGridViewCellEventArgs e)
        {
 
        }
        }
    }
_________
тега [CSHARP] на форуме нет. Используйте универсальный тег [CODE] .. [ /CODE]

Модератор.
Изображения
Тип файла: jpg IMG_0559.jpg (121.4 Кб, 154 просмотров)
Тип файла: jpg Снимок.JPG (28.3 Кб, 240 просмотров)

Последний раз редактировалось Serge_Bliznykov; 24.02.2013 в 18:57.
Wanz вне форума Ответить с цитированием
Старый 24.02.2013, 16:47   #2
Демик
Форумчанин
 
Аватар для Демик
 
Регистрация: 30.01.2011
Сообщений: 231
По умолчанию

Советую почитать про алгоритмы нахождения пути(pathfind) Например, Волновой алгоритм, алгорит A*(A-star), алгоритм Дейкстры.
Злостный анимешнег =^.^=
Демик вне форума Ответить с цитированием
Старый 24.02.2013, 17:04   #3
phomm
personality
Старожил
 
Аватар для phomm
 
Регистрация: 28.04.2009
Сообщений: 2,876
По умолчанию

Поглядите http://programmersforum.ru/showthread.php?t=211804 , я там помогал товарищу с волновым как раз разобраться, маршрутный же вроде как более частный вариант волнового.

Если будут вопросы или там траблы какие, кидайте проект сразу архивом - помогу разобраться.

И маленькое замечание, теги кода не делятся по языкам )) просто code -тег, или кнопочку # используйте.

Последний раз редактировалось phomm; 24.02.2013 в 17:07.
phomm вне форума Ответить с цитированием
Старый 25.02.2013, 19:10   #4
Wanz
 
Регистрация: 24.02.2013
Сообщений: 8
По умолчанию

Цитата:
Сообщение от phomm Посмотреть сообщение
Поглядите http://programmersforum.ru/showthread.php?t=211804 , я там помогал товарищу с волновым как раз разобраться, маршрутный же вроде как более частный вариант волнового.

Если будут вопросы или там траблы какие, кидайте проект сразу архивом - помогу разобраться.

И маленькое замечание, теги кода не делятся по языкам )) просто code -тег, или кнопочку # используйте.
Архив закинул. Печально, но беда в том что я даже не знаю что мне спросить и с чего начать,спасибо за ссылку на тему, сейчас буду глядеть...

Из информации имею только эту фотографию. Гугл мало чем помог.
Вложения
Тип файла: rar WindowsFormsApplication2.rar (37.0 Кб, 63 просмотров)

Последний раз редактировалось Wanz; 25.02.2013 в 19:31.
Wanz вне форума Ответить с цитированием
Старый 26.02.2013, 16:27   #5
phomm
personality
Старожил
 
Аватар для phomm
 
Регистрация: 28.04.2009
Сообщений: 2,876
По умолчанию

Код, конечно, жуткий, всё в одном обработчике клика кнопки. Курите то , что я дал - там норм код по классам разнесён и всё такое. Прикрутите к датагриду просто. А картинка ничего не говорит вообще, алгоритм расписан, извиняюсь , по-дурацки, если это вообще рабочий алгоритм - тупо по расстоянию до конечной точки определять найден ли путь ? Ерунда какая-то, ибо пример подобран. Поставить вместо 7 препятствие - и куда прикажете пойти алгоритму ? а если ещё продлить стену справа от 7? Алгоритм должен бы пойти назад, но описание не предусматривает этого.
phomm вне форума Ответить с цитированием
Старый 26.02.2013, 20:36   #6
Wanz
 
Регистрация: 24.02.2013
Сообщений: 8
По умолчанию

Код жуткий, это да. А фотография...увы большего я не нашел. Препод говорит "у тебя интересная тема" я ей "по ней нет информации" она гнет свое и все. В общем спасибо за помощь. Буду разбираться. Кстати, так как я полнейший ламер и не особо разбираюсь в коде...можете помочь с кодом из той темы?
Код:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AStarInMatrix
{
    class Pathfinde
    {
        private int MapWidht;
        private int MapHeight; 
        private int[,] Map;
        int[,] WayMap;
        public void ReadMap()
        {
            string[] s = System.IO.File.ReadAllLines("level.txt");
            Map = new int[s.Length,s[0].Length];
            for (int i = 0; i < s.Length; i++)
            {
                for (int j = 0; j < s[0].Length; j++)
                {
                    Map[i,j] = (int)char.GetNumericValue(s[i][j]);
                }
            }
            MapWidht = s[0].Length;
            MapHeight = s.Length;
            for (int y = 0; y < MapHeight; y++)
            {
                Console.WriteLine();
                for (int x = 0; x < MapWidht; x++)
                    if (Map[y, x] == 1)
                        Console.Write("+");
                    else
                        Console.Write(" ");
            }
            Console.ReadKey();
        }
           public void FindWave(int startX, int startY, int targetX, int targetY)
        {

            bool add = true;
            int[,] cMap = new int[MapWidht, MapHeight];
            int x, y, step = 0;
            for (y = 0; y < MapHeight; y++)
                for (x = 0; x < MapWidht; x++)
                {
                    if (Map[y,x] == 1)
                        cMap[x,y] = -2;//индикатор стены
                    else
                        cMap[x,y] = -1;//индикатор еще не ступали сюда
                }
            cMap[targetX, targetY] = 0;//Начинаем с финиша
            while (add == true)
            {
                add = false;
                for (y = 0; y < MapHeight; y++)
                    for (x = 0; x < MapWidht ; x++)
                    {
                        if (cMap[x, y] == step)
                        {
                            //Ставим значение шага+1 в соседние ячейки (если они проходимы)
                            if (y - 1 >= 0 && cMap[x - 1, y] != -2 && cMap[x - 1, y] == -1)
                                cMap[x - 1, y] = step + 1;
                            if (x - 1 >= 0 && cMap[x, y - 1] != -2 && cMap[x, y - 1] == -1)
                                cMap[x, y - 1] = step + 1;
                            if (y + 1 < MapWidht && cMap[x + 1, y] != -2 && cMap[x + 1, y] == -1)
                                cMap[x + 1, y] = step + 1;
                            if (x + 1 < MapHeight && cMap[x, y + 1] != -2 && cMap[x, y + 1] == -1)
                                cMap[x, y + 1] = step + 1;
                        }
                    }
                step++;
                add = true;
                if (cMap[startX, startY] != -1)//решение найдено
                    add = false;
                if (step > MapWidht * MapHeight)//решение не найдено
                    add = false;
                //Отрисовка
                for (y = 0; y < MapHeight; y++)
                {
                    Console.WriteLine();
                    for (x = 0; x < MapWidht; x++)
                        if (cMap[x, y] == -1)
                            Console.Write(" ");
                        else
                            if (cMap[x,y] == -2)
                                Console.Write("#");
                            else
                                if (y == startY && x == startX)
                                    Console.Write("S");
                                else
                                    if (y == targetY && x == targetX)
                                        Console.Write("F");
                                    else
                                        if (cMap[y, x] > -1)
                                            Console.Write("{0}", cMap[y, x]);

                }
                Console.ReadKey();
            }
        }
    }
}
Создаю консольное приложение. Вставляю код....ии
Ошибка 1 Программа "C:\Users\Wanz\AppData\Local\Tempor ary Projects\AStarInMatrix\obj\Debug\AS tarInMatrix.exe" не содержит статического метода "Main", подходящего для точки входа AStarInMatrix

Вопрос: Как откомпилировать и куда прикрутить
Код:
static void Main(string[] args)
?
Wanz вне форума Ответить с цитированием
Старый 26.02.2013, 21:07   #7
phomm
personality
Старожил
 
Аватар для phomm
 
Регистрация: 28.04.2009
Сообщений: 2,876
По умолчанию

Вот как один товарищ приспособил тот код http://programmersforum.ru/showthread.php?t=226916
А в оригинальной теме не нашёл консольного проекта.. только все с формами остались, странно, я думал один из них консольный там...
phomm вне форума Ответить с цитированием
Старый 26.02.2013, 21:21   #8
Wanz
 
Регистрация: 24.02.2013
Сообщений: 8
По умолчанию

Еще раз спасибо. Не догоняю. Под оригинальной темой вы подразумевали ее?
http://programmersforum.ru/showthread.php?t=211804
Wanz вне форума Ответить с цитированием
Старый 17.03.2013, 18:55   #9
Wanz
 
Регистрация: 24.02.2013
Сообщений: 8
По умолчанию

С помощью Phomm (фактически написал за меня неуча ленивого всю прогу) удалось таки добить волновой алгоритм.
Код:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        int[,] Map;
        int MapWidht = 10;//ширина
        int MapHeight = 10;//высота
        public Form1()
        {
            InitializeComponent();
        }
        int[,] cMap;
        private void button1_Click(object sender, EventArgs e)
        {
            dataGridView1.RowCount = 10;
            dataGridView1.ColumnCount = 10;

            Map = new int[,]{
                {1,1,1,1,1,1,1,1,1,1},           
                {1,0,0,0,0,0,0,1,0,1},
                {1,0,1,0,0,1,1,0,0,1},
                {1,0,0,0,0,0,0,0,0,1},
                {1,0,0,1,0,1,1,1,0,1},
                {1,0,0,1,0,1,1,1,0,1},           //карта
                {1,0,0,1,0,0,0,0,0,1},
                {1,0,0,0,0,1,0,1,0,1},
                {1,0,0,0,0,0,0,0,0,1},
                {1,1,1,1,1,1,1,1,1,1},
            };
            cMap = new int[MapHeight, MapWidht];

            for (int y = 0; y < MapHeight; y++)
            {
                dataGridView1.Columns[y].Width = 25;  //задаю ширину столбцов
                dataGridView1.Rows[y].Cells[0].Value = "";
                for (int x = 0; x < MapWidht; x++)
                    if (Map[y, x] == 1)
                        dataGridView1.Rows[y].Cells[x].Value = "+";
                    else
                        dataGridView1.Rows[y].Cells[x].Value = " ";
            }

            FindWave(1, 1, 8, 8);//стартовая и финишная позиции

            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == " ")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Black;
                    }
                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "S")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Red;
                    }
                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "F")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.SeaGreen;

                    }
                }
            }
        }

        public void FindWave(int startX, int startY, int targetX, int targetY)
        {
            bool add = true;
            int x, y, step = 0;
            for (y = 0; y < MapHeight; y++)
                for (x = 0; x < MapWidht; x++)
                {
                    if (Map[y, x] == 1)
                        cMap[y, x] = -2;//индикатор стены
                    else
                        cMap[y, x] = -1;//индикатор еще не ступали сюда
                }
            cMap[targetY, targetX] = 0;//Начинаем с финиша
            while (add == true)
            {
                add = false;
                for (y = 0; y < MapWidht; y++)
                    for (x = 0; x < MapHeight; x++)
                    {
                        if (cMap[x, y] == step)
                        {
                            //Ставим значение шага+1 в соседние ячейки (если они проходимы)
                            if (y - 1 >= 0 && cMap[x, y - 1] != -2 && cMap[x, y - 1] == -1)
                                cMap[x, y - 1] = step + 1;
                            if (x - 1 >= 0 && cMap[x - 1, y] != -2 && cMap[x - 1, y] == -1)
                                cMap[x - 1, y] = step + 1;

                            if (y + 1 < MapWidht && cMap[x, y + 1] != -2 && cMap[x, y + 1] == -1)
                                cMap[x, y + 1] = step + 1;
                            if (x + 1 < MapHeight && cMap[x + 1, y] != -2 && cMap[x + 1, y] == -1)
                                cMap[x + 1, y] = step + 1;
                        }
                    }
                step++;
                add = true;
                if (cMap[startY, startX] != -1)//решение найдено
                    add = true;
                if (step > MapWidht * MapHeight)//решение не найдено
                    add = false;
            }
Вложения
Тип файла: rar Volna_rab.rar (67.7 Кб, 146 просмотров)
Wanz вне форума Ответить с цитированием
Старый 17.03.2013, 18:56   #10
Wanz
 
Регистрация: 24.02.2013
Сообщений: 8
По умолчанию

Продолжение

Код:
//Отрисовываем карты
            for (y = 0; y < MapHeight; y++)
            {
                for (x = 0; x < MapWidht; x++)
                    if (cMap[y, x] == -1)
                        dataGridView1.Rows[y].Cells[x].Value = "-1";
                    else
                        if (cMap[y, x] == -2)
                            dataGridView1.Rows[y].Cells[x].Value = " ";
                        else
                            if (y == startY && x == startX)
                                dataGridView1.Rows[y].Cells[x].Value = "S";
                            else
                                if (y == targetY && x == targetX)
                                    dataGridView1.Rows[y].Cells[x].Value = "F";
                                else
                                    if (cMap[y, x] > -1)
                                        dataGridView1.Rows[y].Cells[x].Value = cMap[y, x];
            }
        }
private Point getminneighbour(Point cell)
        {
            Point[] cells = new Point[8];
            int cur = 0;
            int x = 0;
            int y = 0;
            for (int i = 0; i < 4; i++)
            {
                switch (i)
                {
                    case 0: //up
                        x = cell.X;
                        y = cell.Y - 1;
                        break;
                    case 1: // right
                        x = cell.X + 1;
                        y = cell.Y;
                        break;
                    case 2: // down
                        x = cell.X;
                        y = cell.Y + 1;
                        break;
                    case 3: // left
                        x = cell.X - 1;
                        y = cell.Y;
                        break;
                    case 4:
                        x = cell.X + 1;
                        y = cell.Y - 1;
                        break;
                    case 5:
                        x = cell.X + 1;
                        y = cell.Y + 1;
                        break;
                    case 6:
                        x = cell.X - 1;
                        y = cell.Y + 1;
                        break;
                    case 7:
                        x = cell.X - 1;
                        y = cell.Y - 1;
                        break;
                }
                if ((x > 0) && (y > 0) && (x < MapWidht) && (y < MapHeight) && (Map[y, x] == 0))
                    cells[cur++] = new Point(x, y);
            }
 


            Point res = cells[0];
            for (int i = 1; i < cur; i++)
            {
                if (cMap[cells[i].Y, cells[i].X] < cMap[res.Y, res.X])
                    res = cells[i];
            }
            return res;
        }

        private void button2_Click(object sender, EventArgs e)
        {
            Point cur = new Point(1, 1);
            while (dataGridView1.Rows[cur.Y].Cells[cur.X].Value.ToString() != "F")
            {
                int x = cur.X;
                int y = cur.Y;
                cur = getminneighbour(cur);
                dataGridView1.Rows[y].Cells[x].Value = "o";
                dataGridView1.Rows[1].Cells[1].Value = "S";
                if (dataGridView1.Rows[y].Cells[x].Value.ToString() == "o")
                { dataGridView1.Rows[y].Cells[x].Style.BackColor = System.Drawing.Color.Orange; };
                
            }
           
            for (int y = 0; y < MapWidht; y++)
                for (int x = 0; x < MapHeight; x++)
                { dataGridView1.Rows[y].Cells[x].Value = " "; }
        }

    }
}
Всем спасибо за участие и помощь. Тема закрыта.
Wanz вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск пути (алгоритм А* / Дейкстра) Alex11223 Общие вопросы по программированию, компьютерный форум 2 01.02.2012 10:50
Поиск кратчайшего пути в лабиринте Java Omnikus Фриланс 1 15.12.2011 20:46
swi prolog. поиск пути в лабиринте. tatysya Помощь студентам 1 15.05.2011 18:36
Поиск пути в лабиринте - Пролог yulia Помощь студентам 15 21.08.2010 00:14
Поиск пути в лабиринте s2dentishe Помощь студентам 2 13.03.2010 18:36