За последние 24 часа нас посетили 17960 программистов и 1654 робота. Сейчас ищут 1369 программистов ...

Помогите пожалуйста в решении задачи: Добавить квадрат (3х3)

Тема в разделе "Решения, алгоритмы", создана пользователем garmonkz, 8 авг 2009.

  1. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    Помогите пожалуйста в решении задачи, третий день сижу а вместо решения получил только головную боль. :x
    Задача: Добавить квадрат (3х3) на пустое место, занятые квадраты хранятся в базе (id, y, x). У каждого квадрата есть центр (x%3=0, y%3=0). При каждом добавлении, должна забиваться база, т.е. в базу забиваются координаты новых девяти квадратов с центром. При этом есть switch, который определяет направление нового квадрата, case’ов 8 (север, юг, восток, запад, св, сз, юв, юз).
    [​IMG]

    На рисунке я показал примерное расположение координатной сетки с квадратами (указаны только координаты центров). Добавляться должны ближайшие квадраты (отмечены вопросиками), и когда квадрат добавлен, сетка расширяется до бесконечности. В общем «вакантной» зоной является оболочка.
     
  2. kostyl

    kostyl Guest

    Код в студию
     
  3. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    Переформулируй более понятно, желательно с картинками нескольких возможных вариантов. Потому как телепатор обнаруживает слишком много вариантов :)
    Игру делаешь?
     
  4. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    Вот экспорт базы:[sql]
    -- phpMyAdmin SQL Dump
    -- version 2.11.3
    -- http://www.phpmyadmin.net
    --
    -- Хост: localhost
    -- Время создания: Авг 08 2009 г., 22:55
    -- Версия сервера: 4.1.8
    -- Версия PHP: 4.3.10

    SET SQL_MODE="NO_AUTO_VALUE_ON_ZERO";

    --
    -- База данных: `exp`
    --

    -- --------------------------------------------------------

    --
    -- Структура таблицы `exp_territory`
    --

    CREATE TABLE IF NOT EXISTS `exp_territory` (
    `id` int(10) NOT NULL auto_increment,
    `x` int(10) NOT NULL default '0',
    `y` int(10) default NULL,
    `country_id` int(10) default NULL,
    `land` char(2) default NULL,
    `buildings` varchar(10) default NULL,
    PRIMARY KEY (`id`)
    ) ENGINE=MyISAM DEFAULT CHARSET=cp1251 AUTO_INCREMENT=17 ;

    --
    -- Дамп данных таблицы `exp_territory`
    --

    INSERT INTO `exp_territory` (`id`, `x`, `y`, `country_id`, `land`, `buildings`) VALUES
    (14, -1, -1, 1, '1', '1'),
    (13, 1, 0, 1, '1', '1'),
    (12, 0, 0, 1, '1', '1'),
    (11, -1, 0, 1, '0', '1'),
    (10, 1, 1, 1, '1', '1'),
    (9, 0, 1, 1, '1', '1'),
    (1, -1, 1, 1, '1', '1'),
    (15, 0, -1, 1, '1', '1'),
    (16, 1, -1, 1, '1', '1');
    [/sql]

    Код рытый перерытый, затирал и начинал заново раз 7, вот что есть:
    PHP:
    1. class Territory
    2. {
    3.     function CreateTerritory($side,$userid)
    4.     {
    5.         $db = new DB;
    6.         $max_min = $db->SetQuery("select min(x) minx, max(x) maxx, min(y) miny, max(y) maxy from exp_territory where x%3=0 and y%3=0");
    7.         $width = (abs($max_min[0]->minx)+abs($max_min[0]->maxx));
    8.         $heigth = (abs($max_min[0]->miny)+abs($max_min[0]->maxy));
    9.         $range_x = floor(($width)/6);
    10.         if ($range_x==0) $range_x=1;
    11.         $range_y = floor(($heigth)/6);
    12.         if ($range_y==0) $range_y=1;
    13.         $coor = array();
    14.         print 'Range '.$range_x.'<br>';
    15.         switch($side)
    16.         {
    17.             case 1:
    18.  
    19.                 break;
    20.             case 2:
    21.                
    22.                 break;
    23.             case 3:
    24.                
    25.                 break;
    26.             case 4:
    27.                
    28.                 break;
    29.             case 5:
    30.                
    31.                 break;
    32.             case 6:
    33.                
    34.                 break;
    35.             case 7:
    36.                
    37.                 break;
    38.             case 8:
    39.                
    40.                 break;
    41.             default:
    42.                 return -1;
    43.         }
    44.     }
    45. }
     
  5. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    Да, пытаюсь делать игру, а эта задача будет раздавать земли (участки) новым игрокам, т.е. тут фигуры могут быть самые разные. Главное это, не может быть прорех, или как правильно сказать, «вакантных» квадратов, окруженными занятыми. Вот…
    Картинки прикрепляю 2. Первыя показывает switch, case. Вторая это возможные варианты фигур, по просьбе antonn’a.
    1. [​IMG]
    2. [​IMG]
     
  6. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    выбор идет по одному квадрату в каждую сторону? :)
    а то своими 3*3 запутал.

    на второй картинке нумер 5 частный случай нумера 3 на той же картинке :)
     
  7. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    как вариант - всегда иметь рамку вокруг поля (да, тут поле конечное) и при выборе новой земли обсчитывать окружающие поля - если находим пустое поле то искать путь до этой белой рамки (например Дейкстрой). Если не найдет пути - значит область внутри захваченных земель.
     
  8. Kreker

    Kreker Старожил

    С нами с:
    8 апр 2007
    Сообщения:
    5.433
    Симпатии:
    0
    Первое, что приходит в голову - четыре массива с незанятыми квадратами, по два на каждую ось: один с положительными координатами, другой - с модулем отрицательных координат.
    Сначала ищем координату по одной оси, затем по другой. Поиск координаты достаточно прост: выталкиваем первое значение массива из положительных и отрицательных координат, смотрим, что меньше, то и ближе к центру, а значит - правильнее.
    Надеюсь, что правильно понял задачу.
     
  9. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    вот как бы я это сделал в дельфи http://desksoft.ru/index.php?downloads= ... nts&id=229
    (ищет только вверх/вниз/право/лево, без диагоналей)
    Плюсы - поиск по всему полю, не даст окружить точку в другой стороне карты, минусы - карта конечна. Как это оптимально перенести в ПХП и на базы - без понятия :)
    Зайти еще в какой нить форум геймдева, может там подскажут

    PS и еще один момент - она делает поиск до точки (1,1) которая всегда должна быть свободна :)
     
  10. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    :) Да квадрат выбирается только 1, центр 9-ти квадратов. Он отсеивается условием (x%3=0, y%3=0).
    И насчет картинки: Видишь ли я хотел показать выбор СЮ, СЗ, ЮВ, ЮЗ если до этого выбирали только С или толь Ю. Не должно быть 2.2.3, в случае подобной ситуации должно быть 2.1.3
     
  11. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    Спасибо правильно понял, я уже и это делал но с реализацией возник проблемы.
     
  12. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    просто так смотреть ближайшие квадраты нельзя, если тебе действительно нужно, чтобы нельзя было окружить точку.
    Например такой вариант:
    Код (Text):
    1. 00000
    2. 01110
    3. 01010
    4. 01010
    5. 01*10
    6. 00000
    ты хочешь захватить точку показанную звездочкой. Обходя только ближайшие точки ты не увидишь как захватится точка в тупике, потому я и навернул волновой поиск путей
     
  13. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    antonn
    Вроде получилось,:idea:
    и

    Я добавил еще одну таблицу "vacancy" и забил ее 8 квадратами которые граничат с самым 1-м квадратом. И вот что получилось. Проверял, вроде работает.
    PHP:
    1. class Territory
    2. {
    3.     function CreateTerritory($side,$userid)
    4.     {
    5.         $db = new DB;
    6.         $txt = '<table border="0"><form action="index.php?id=5" method="post" name="terr_chose" ><tr><td>№</td><td>Выб.</td><td>Край света</td><td>Долгота</td><td>Широта</td></tr>';
    7.         switch($side)
    8.         {
    9.             case 1:
    10.             $vacancy = $db->SetQuery("select x,y from exp_vacancy where y>0 and y>(sqrt(x*x))");
    11.             srand ((float)microtime()*100);
    12.             shuffle ($vacancy);
    13.             for ($i=0;$i<count($vacancy);$i++)
    14.             {
    15.                 $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Север от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    16.                 if ($i>5) break;
    17.             }
    18.                 break;
    19.             case 2:
    20.                 $vacancy = $db->SetQuery("select x,y from exp_vacancy where y>0 and x>0");
    21.             srand ((float)microtime()*100);
    22.             shuffle ($vacancy);
    23.             for ($i=0;$i<count($vacancy);$i++)
    24.             {
    25.                 $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Северо-запад от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    26.                 if ($i>5) break;
    27.             }
    28.                 break;
    29.             case 3:
    30.             $vacancy = $db->SetQuery("select x,y from exp_vacancy where x>0 and x>(sqrt(y*y))");
    31.             srand ((float)microtime()*100);
    32.             shuffle ($vacancy);
    33.             for ($i=0;$i<count($vacancy);$i++)
    34.             {
    35.                 $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Восток от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    36.                 if ($i>5) break;
    37.             }
    38.                 break;
    39.             case 4:
    40.             $vacancy = $db->SetQuery("select x,y from exp_vacancy where y<0 and x>0");
    41.             srand ((float)microtime()*100);
    42.             shuffle ($vacancy);
    43.             for ($i=0;$i<count($vacancy);$i++)
    44.             {
    45.                 $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Юго-запад от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    46.                 if ($i>5) break;
    47.             }
    48.                 break;
    49.             case 5:
    50.             $vacancy = $db->SetQuery("select x,y from exp_vacancy where y<0 and (sqrt(x*x))<(sqrt(y*y))");
    51.             srand ((float)microtime()*100);
    52.             shuffle ($vacancy);
    53.             for ($i=0;$i<count($vacancy);$i++)
    54.             {
    55.                 $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Юг от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    56.                 if ($i>5) break;
    57.             }
    58.                 break;
    59.             case 6:
    60.                 $vacancy = $db->SetQuery("select x,y from exp_vacancy where y<0 and x<0");
    61.                 srand ((float)microtime()*100);
    62.                 shuffle ($vacancy);
    63.                 for ($i=0;$i<count($vacancy);$i++)
    64.                     {
    65.                         $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Юго-запад от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    66.                         if ($i>5) break;
    67.                     }
    68.                 break;
    69.             case 7:
    70.                 $vacancy = $db->SetQuery("select x,y from exp_vacancy where x<0 and (sqrt(x*x))>(sqrt(y*y))");
    71.                 srand ((float)microtime()*100);
    72.                 shuffle ($vacancy);
    73.                 for ($i=0;$i<count($vacancy);$i++)
    74.                     {
    75.                         $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Запад от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    76.                         if ($i>5) break;
    77.                     }
    78.                 break;
    79.             case 8:
    80.                 $vacancy = $db->SetQuery("select x,y from exp_vacancy where x<0 and y>0");
    81.                 srand ((float)microtime()*100);
    82.                 shuffle ($vacancy);
    83.                 for ($i=0;$i<count($vacancy);$i++)
    84.                     {
    85.                         $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Северо-запад от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    86.                         if ($i>5) break;
    87.                     }
    88.                 break;
    89.             default:
    90.                 return -1;
    91.         }
    92.         print $txt.'</table><input type="submit" name="Submit" class="button" value="Сохранить" /></form>';
    93.     }
    94.     function CreateVacancy($xx,$yy)
    95.     {
    96.         $db = new DB;
    97.         $uje_est = $db->SetQuery("select x,y from exp_territory where (x%3=0 and y%3=0) and (x=".$xx."-3 or x=".$xx."+3 or y=".$yy."-3 or y=".$yy."+3)");
    98.         $vacs = $db->SetQuery("select x,y from exp_vacancy where (x=".$xx."-3 or x=".$xx."+3 or y=".$yy."-3 or y=".$yy."+3)");
    99.         $uje_est = array_merge($uje_est, $vacs);
    100.         $coors_busy = array();
    101.         for ($i=0; $i<count($uje_est);$i++)
    102.         {
    103.             $coors_busy[$i]=$uje_est[$i]->x.$uje_est[$i]->y;
    104.         }
    105.         if (!in_array(($xx).($yy+3),$coors_busy)) $db->InsertQuery("INSERT INTO exp_vacancy (x,y) VALUES ('".($xx)."','".($yy+3)."')");
    106.         if (!in_array(($xx+3).($yy+3),$coors_busy)) $db->InsertQuery("INSERT INTO exp_vacancy (x,y) VALUES ('".($xx+3)."','".($yy+3)."')");
    107.         if (!in_array(($xx+3).($yy),$coors_busy)) $db->InsertQuery("INSERT INTO exp_vacancy (x,y) VALUES ('".($xx+3)."','".($yy)."')");
    108.         if (!in_array(($xx+3).($yy-3),$coors_busy)) $db->InsertQuery("INSERT INTO exp_vacancy (x,y) VALUES ('".($xx+3)."','".($yy-3)."')");
    109.         if (!in_array(($xx).($yy-3),$coors_busy)) $db->InsertQuery("INSERT INTO exp_vacancy (x,y) VALUES ('".($xx)."','".($yy-3)."')");
    110.         if (!in_array(($xx-3).($yy-3),$coors_busy)) $db->InsertQuery("INSERT INTO exp_vacancy (x,y) VALUES ('".($xx-3)."','".($yy-3)."')");
    111.         if (!in_array(($xx-3).($yy),$coors_busy)) $db->InsertQuery("INSERT INTO exp_vacancy (x,y) VALUES ('".($xx-3)."','".($yy)."')");
    112.         if (!in_array(($xx-3).($yy+3),$coors_busy)) $db->InsertQuery("INSERT INTO exp_vacancy (x,y) VALUES ('".($xx-3)."','".($yy+3)."')");
    113.         $db->InsertQuery("DELETE FROM exp_vacancy WHERE x=".$xx." and y=".$yy."");
    114.     }
    115. }
    Тут две функции, CreateTerritory($side,$userid) - отвечает за поиск "вакантных мест", а CreateVacancy($xx,$yy) - создает вакантные места, в зависимости от новозанятой территории ($xx,$yy).

    Спасибо огромное, хорошенько покурил, погулял сел и как запор прорвало :D :D
     
  14. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    исчо раз повторю - ты смоделировал ситуацию которую я обрисовал циферками? :)
     
  15. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    Да тут ты прав... Но в том алгоритме, который предлагал ты возможна такая ситуация:
    [​IMG]

    т.е. соседей не будет вовсе. :(

    А что если в запросе к базе добавить order by и убрать shuffle :?:
    Что то типа:
    PHP:
    1. $vacancy = $db->SetQuery("select x,y from exp_vacancy where y>0 and y>(sqrt(x*x)) ORDER BY Y DESC");
    2.              for ($i=0;$i<count($vacancy);$i++)
    3.              {
    4.                  $txt .= '<tr><td>'.($i+1).'</td><td><input name="terr_new" type="radio" value="'.$vacancy[$i]->x.$vacancy[$i]->y.'" /></td><td>Север от Центра Мира</td><td>'.$vacancy[$i]->x.'</td><td>'.$vacancy[$i]->y.'</td></tr>';
    5.                  if ($i>5) break;
    6.              }
    Это когда юзер будет регится, то ему будет предлагаться самые "низкие" варианты, в первую очередь.
     
  16. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    не понял по скрину - ну такое возможно в алгоритме, а не должно быть? я то это поправлю в пяток строк, не проблема, а вот на пхп все это перевести... :)
     
  17. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    В принципе пойдет, главное вакантные места останутся вакантными, и когда нибудь кто нибудь их займет. Можно правда ускорить этот процесс, но это позже. antonn ты не разбираешься в GD? Как теперь можно все это хозяйство запечатлеть на изображении? Если нетрудно примерчик какой нибудь... Хотя бы одной фигуры из [​IMG] разными цветами.
     
  18. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    не, с GD я толком не разбирался, но можешь поискать тут по форуму - был пример рисования колец олимпиады с АА, там попиксельное рисование вроде как (не помню) :)
     
  19. kostyl

    kostyl Guest

    antonn
    Да тебе пора уже с него бабло брать...
     
  20. garmonkz

    garmonkz Активный пользователь

    С нами с:
    8 авг 2009
    Сообщения:
    10
    Симпатии:
    0
    Адрес:
    Актобе, Казахстан
    kostyl
    Спасибо тебе добрый человек. Лучше б посоветовал чего нибудь, но конечно не в этом направлении, а в направлении типа "Добавить квадрат (3х3)"
     
  21. antonn

    antonn Активный пользователь

    С нами с:
    10 июн 2007
    Сообщения:
    2.996
    Симпатии:
    0
    kostyl
    за что? :)