Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++ Builder
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.90/10: Рейтинг темы: голосов - 10, средняя оценка - 4.90
QVO
644 / 455 / 80
Регистрация: 26.10.2010
Сообщений: 1,263
Записей в блоге: 4
Завершенные тесты: 3
#1

Алгоритм Кегелеса-Рауера для поиска кратчайшего пути

07.08.2011, 23:21. Просмотров 1831. Ответов 5
Метки нет (Все метки)

Здравствуйте, пару дней назад реализовал алгоритм Кегелеса-Рауера для поиска кратчайшего пути.
Сегодня решил внедрить его в игру и получил жуткие тормоза.

Этим участком кода я строю волну от персонажа [1 до n]

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
    int row         = 0;  // строка массива
  int col         = 0;  // столбец массива
  int i           = 0;  // счетчик итераций циклов
  int count_zero  = 0;  // количество элементов массива со значением 0
                        // для определения верхнего предела цикла замены
                        // нулей рабочими значениями
  int value       = 0;  // значение текущего элемента массива
  int feld_height = 40; // ширина массива
  int feld_width  = 40; // высота массива
 
  // Обнуляю
    for (col = 1; col < feld_width-1; col++)
  {
    for (row = 1; row < feld_height-1; row++)
    {
       if (MoveGrid->Cells[row][col].ToInt() > 0)
       {
        MoveGrid->Cells[row][col] = "0";
       }
    }
  }
  
   // Задаю значение для элемента массива соответствующего точке финиша
  MoveGrid->Cells[abs(X/32)][abs(Y/32)] = "1";
 
  // Определяю количество элементов массива с нулевыми значениями.
  // Это нужно для того, чтобы задать верхнюю границу следующего цикла,
  // заполняющего массив значениями. В любом случае число его
  // итераций не может превышать количества нулевых элементов.
  for (col = 1; col < feld_width-1; col++)
  {
    for (row = 1; row < feld_height-1; row++)
    {
       if (MoveGrid->Cells[row][col].ToInt() == 0)
       {
        count_zero++;
       }
    }
  }
  // Заменяю нулевые значения массива соответствующими числами.
  for (i = 1; i < count_zero; i++)
  {
    value++;
    for (col = 1; col < feld_width-1; col++)
    {
      for (row = 1; row < feld_height-1; row++)
      {
        if (MoveGrid->Cells[row][col].ToInt() == value)
        {
          if (MoveGrid->Cells[row + 1][col].ToInt() == 0) { MoveGrid->Cells[row + 1][col] = IntToStr(value + 1);}
          if (MoveGrid->Cells[row - 1][col].ToInt() == 0) { MoveGrid->Cells[row - 1][col] = IntToStr(value + 1);}
          if (MoveGrid->Cells[row][col + 1].ToInt() == 0) { MoveGrid->Cells[row][col + 1] = IntToStr(value + 1);}
          if (MoveGrid->Cells[row][col - 1].ToInt() == 0) { MoveGrid->Cells[row][col - 1] = IntToStr(value + 1);}
        }
      }
    }
  }
Этот участок кода двигает монстра
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int row         = 0;  // строка массива
  int col         = 0;  // столбец массива
  int value       = 0;  // значение текущего элемента массива
 
 
  // Сохраняю в переменной value значение элемента массива,
  // соответствующего точке старта.
  value = MoveGrid->Cells[abs(X/32)][abs(Y/32)].ToInt();
 
  // Прокладываю путь, последовательно спускаясь по клеткам поля
  // от значения соответствующего точке старта точке финиша.
  col = abs(X/32);
  row = abs(Y/32);
 
  do
  {
    if (MoveGrid->Cells[row][col].ToInt() == value)
    {
      value--;
      if (MoveGrid->Cells[row + 1][col].ToInt() == value)
      {
        row++;
        X++;
      }
      else if (MoveGrid->Cells[row - 1][col].ToInt() == value)
      {
        row--;
        X--;
      }
      else if (MoveGrid->Cells[row][col + 1].ToInt() == value)
      {
         col++;
         Y++;
      }
      else if (MoveGrid->Cells[row][col - 1].ToInt() == value)
      {
        col--;
        Y--;
      }
    }
  }while(value >= 2);
Подскажите как быть? Сдвигать монстра по X и Y не вариант, так как ландшафт на карте сложный и он может воткнуться в стену и стоять...
Я обрезал карту по камере и обрабатывал в цикле только те ячейки которые видны в данный момент.
В отдельный таймер засунул построение волны с интервалом 16мс(размер тайла разделил на скорость), но желаемого эффекта это не дало.
Игра через каждых 16мс подвисает.

P.S пардон, в коде были мои комментарии на завтрашний день чтобы не забыть.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.08.2011, 23:21
Ответы с готовыми решениями:

Алгоритм поиска пути A*
использую библиотеку SFML только для окна пытался сделать алгоритм поиска пути...

Нахождение кратчайшего пути графа
Товарищи программисты! Помогите пожалуйста! Очень нужна программа на С++...

GPS и поиск кратчайшего пути
Здравствуйте, столкнулся с такой проблемой, хочу сделать GPS, простенькую...

Создание графа по матрице и поиск кратчайшего пути из одного графа в другой
Доброго времени суток. Задали задание по матрице составить граф и написать...

Нужен исх. "поиск кратчайшего пути на графе"
помогите плиз.

5
QVO
644 / 455 / 80
Регистрация: 26.10.2010
Сообщений: 1,263
Записей в блоге: 4
Завершенные тесты: 3
08.08.2011, 00:55  [ТС] #2
Вот так оно должно работать в игре (картинка с права)

Вроде разобрался, завтра попробую. Думаю нужно цикл do while убрать.
0
Миниатюры
Алгоритм Кегелеса-Рауера для поиска кратчайшего пути  
Вложения
Тип файла: rar Project1.rar (224.7 Кб, 78 просмотров)
VTsaregorodtsev
517 / 445 / 67
Регистрация: 19.02.2010
Сообщений: 1,715
13.08.2011, 22:39 #3
***** использовать текстовый грид и тратить из-за этого кучу времени на конверсии целого в строку и строки в целое. Это раз.
***** использовать грид (компонент) вместо обычного массива - гет- и сет-функции для доступа к элементу грида будут тормознее, чем доступ к элементу массива. Это два.
Если грид использован потому, что не хватает знаний об использовании указателей (для реализации двумерного массива) - это полный [censored]. ***** привыкать использовать неоптимальные "высокоуровневые" решения только из-за того, что не освоены основы языка программирования.

 Комментарий модератора 
VTsaregorodtsev, Правила
3.2. Запрещено использовать нецензурные выражения в любом виде, оскорблять других участников форума, умышленно использовать выражения, противоречащие правилам русского языка.
Прекратите провоцировать пользователей.

Устное предупреждение.
0
SalterOk
13.08.2011, 22:49
  #4

Не по теме:

а повежливее никак?

0
QVO
644 / 455 / 80
Регистрация: 26.10.2010
Сообщений: 1,263
Записей в блоге: 4
Завершенные тесты: 3
14.08.2011, 10:55  [ТС] #5
VTsaregorodtsev, использую в качестве удобства загрузки карты. Уже все реализовал и без вашего совета.
0
lavrv
0 / 0 / 0
Регистрация: 15.01.2012
Сообщений: 4
15.01.2012, 17:07 #6
Добрый день, не могли бы вы выложить исходник данной программы?
0
15.01.2012, 17:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.01.2012, 17:07

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками...

Программа поиска пути в лабиринте
Здравствуйте! Задали в универе написать программу на Билдере, которая бы искала...

алгоритм поиска
Вообщем есть алгоритм который ищет файлы на пк, по формату и имени : void...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru