Определение допустимых перемещений по сетке - PullRequest
2 голосов
/ 03 февраля 2009

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

grid layout

Если предположить, что фигура 1 находится в позиции a1, а фигура 2 в позиции c3, как я могу определить, какие квадраты сетки являются допустимыми движениями, если фигура 1 может двигаться (скажем, 3 квадрата, а фигура 2 может двигаться 2?

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

Если это имеет значение, я пытаюсь сделать это в javascript, но, если честно, я думаю, что моя ошибка здесь - это неспособность правильно осмыслить, а не ошибка в понимании языка.

Обновление - я добавляю первый раунд кода, написанного после публикации приведенных ниже ответов. Я подумал, что людям, находящимся в аналогичной ситуации, может быть полезно увидеть код

Он небрежный и работает только для одного элемента, размещенного на доске, но, по крайней мере, функция check_allowable_moves() работает для этого начального запуска. Для тех из вас, кто задается вопросом, какого черта я создаю эти странные буквенно-цифровые объекты, а не просто использую числовую ось X и Y - это потому, что идентификатор в HTML не может начинаться с цифры. Фактически, притворство, что я может использовать числа для запуска идентификаторов, очень помогло понять функциональность и концепции, описанные в фантастических ответах, которые я получил.

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="application/xhtml+xml;utf-8"/>

<title>Test page</title>
<style> 

    #chessboard { clear: both; border:solid 1px black; height: 656px; 
                  width:656px; /*width = 8*40 + 16 for border*/ }
    #chessboard .row { overflow: auto; clear: both; }
    #chessboard .row span { display: block; height: 80px; 
                            width: 80px; float: left; 
                            border:solid 1px black; }
    .allowable { background: blue; }
</style>
<script type="text/javascript" src="http://www.google.com/jsapi"></script>
<script type="text/javascript">
    google.load("jquery", "1.2.6");
    google.load("jqueryui", "1.5.3");
</script>
<script type="text/javascript">
$(document).ready(function() {
    (function() {
    var global = this;
    global.Map = function(container) {
        function render_board() {
        var max_rows = 8;
        var cols = new Array('a','b', 'c', 'd', 'e', 'f', 'g', 'h');
        var jqMap = $('<div />');
        jqMap.attr('id', 'chessboard');
        var x=0;
        for(x; x<max_rows; x++) {
            var jqRow = $('<span />');
            jqRow.addClass('row');
            var i=0;
            for(i; i<cols.length; i++) {
                var jqCol = $('<span />');
                jqCol.attr('id', cols[i]+(x+1));
                jqCol.addClass(cols[i]);
                jqRow.append(jqCol);
            }
          jqMap.append(jqRow);
        }
     $('#'+container).append(jqMap);
   }
   function add_piece(where, id) {
     var jqPiece = $('<div>MY PIECE'+id+'</div>');
     var jqWhere = $('#'+where);
     jqPiece.attr('id', 'piece-'+id);
     jqPiece.addClass('army');
     jqPiece.draggable({cursor: 'move',
                              grid:[82, 82],
                              containment: '#chessboard',
                              revert: 'invalid',
                              stop: function(ev, ui) {
                                //console.log(ev.target.id);
                              }
                            });
     jqWhere.append(jqPiece);
     check_allowable_moves(where);
    }
    function check_allowable_moves(location) {
     var x_axis = { 'a':1,'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8 };
     var x_axis_alpha = { 1:'a',2:'b', 3:'c', 4:'d', 5:'e', 6:'f', 7:'g', 8:'h' };
     $('.allowable').droppable("destroy");
     $('.allowable').removeClass('allowable');
     //get the x,y values of the piece just placed
     var x = parseInt(x_axis[location[0]], 10);
     var y = parseInt(location[1], 10);
     var x_min = x-2;
     var y_min = y-2;
      for(x_min; x_min<=x+2; x_min++) {
        for(y_min; y_min<=y+2; y_min++) {
           var jqCell = $('#'+x_axis_alpha[x_min]+y_min)
           jqCell.addClass('allowable');
           jqCell.droppable({ accept: '.army',
              drop: function(ev, ui) {
                //console.log(ev, ui, $(this));
                //handle_drop(ev, ui, $(this));
                check_allowable_moves($(this).attr('id'));
              }
            });
        }
        y_min = parseFloat(y)-2;
      }
    }
    render_board();
    add_piece('d5', '2');
   }
 })();
var map = new Map('content');
});
</script>
</head>

<body id="debug">
    <div id="page">
        <div id="content"> </div>
    </div><!-- end page -->
</body>
</html>

Ответы [ 4 ]

3 голосов
/ 03 февраля 2009

Предположим, кусок p находится в положении x, y и может отодвинуть n квадратов в положение x2, y2. Это означает, что сумма абсолютных разностей между (x - x2) и (y - y2) не может быть больше n.

Если вы собираетесь показать, в какие квадраты можно переместиться (вместо того, чтобы брать вводы x2 и y2), я думаю, что было бы лучше обойти все позиции в квадрате вокруг фигуры. То есть ...

for (x - n TO x + n):
    for (y - n TO x + n):
        if (abs(x - x2) + abs(y - y2) <= n):
            mark as okay.

В этом ответе предполагается, что фигуры могут перемещаться только на соседние квадраты, а не по диагонали.

Редактировать: Если вы хотите диагональное перемещение, и перемещение по диагонали стоит столько же, сколько перемещение по горизонтали или вертикали, тогда проблема на самом деле намного проще - кусок p может перемещаться между диапазонами (x - n, x +) n) и (y - n, y + n).

Ответ становится намного более сложным, если перемещение по диагонали не стоит так дорого, как горизонтальное + вертикальное движение (например, если диагональ стоит 1,5, тогда как h / v стоит 1).

2 голосов
/ 03 февраля 2009

В общем, такие проблемы включают в себя достаточно ограниченную сетку мест, которые можно достичь. Возьмите структуру данных размера сетки и чьи элементы могут содержать количество оставшихся точек движения с достаточной точностью.

Инициализировать сетку для непосещенного значения. Это не должно быть в диапазоне от нуля до максимально возможной скорости движения. Отрицательное значение идеально.

Инициализировать начальную позицию до количества оставшихся ходов.

На данный момент существует три возможных подхода:

1) Повторно сканируйте всю сетку каждый шаг. Просто, но медленнее. Прекращение - это когда очки не дают легального хода.

2) Хранить очки в стеке. Быстрее, чем № 1, но все же не самый лучший. Завершение - когда стек пуст.

3) Хранить очки в очереди. Это лучшее. Завершение - когда очередь пуста.

Repeat
   ObtainPoint {From queue, stack or brute force}
   For Each Neighbor do
      Remaining = Current - MovementCost
      If Remaining > CurrentValue[Neighbor] then
         CurrentValue[Neighbor] = Remaining
         Push or Queue Neighbor
Until Done

Обратите внимание, что при использовании стекового подхода у вас всегда будут случаи, когда вы выбрасываете старые вычисления и выполняете их снова. Подход, основанный на очереди, будет иметь место только в том случае, если есть случаи, когда обход по пересеченной местности дешевле, чем проходить через него.

Проверять условие завершения только в конце цикла или завершать, когда ObtainPoint пытается использовать пустую очередь или стек. Пустая очередь / стек после ObtainPoint НЕ означают, что вы закончили!

(Обратите внимание, что это значительное расширение ответа Иана.)

1 голос
/ 03 февраля 2009

Это чисто на концептуальном уровне, но попробуйте эту логику:

  1. Возьмите все возможные места в одном шаге от начальной точки и поместите их в стек (Moves Taken = 0)

  2. Вытяните один из стека и повторите, используя эту новую координату в качестве новой отправной точки. (Ходы взяты = 1). Вам нужно убедиться, что вы не поместите дубликаты координат в стек

  3. Повторяйте 2, пока не исчерпаете все доступные ходы своей фигуры.

Возможно, я не очень хорошо объясняю это, дайте мне знать, если у вас есть какие-либо вопросы о том, что я пытаюсь сказать.

0 голосов
/ 03 февраля 2009

Вы можете использовать подход, описанный выше, но вместо этого использовать рекурсию.

Рекурсия "глубина" - это расстояние перемещения.

Прорыв, когда глубина> движение.

Каждая итерация должна возвращать вектор пробелов и добавлять свое собственное местоположение.

Удалить дубликаты

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...