Determinare muove ammissibile su una griglia
https://stackoverflow.com/questions/508356
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qualcuno può suggerire un modo adeguato di capire un pezzi muove consentiti su una griglia simile a quella nell'immagine qui sotto.
Supponendo piece1 è in posizione a1 e piece2 è in posizione C3, come posso capire quale griglia piazze sono mosse ammissibile se piece1 può spostare (diciamo) 3 piazze e piece2 può muoversi 2?
Ho passato troppo tempo in via di sviluppo FANGHI testo basato a quanto pare, semplicemente non posso ottenere il mio cervello per fare il passo successivo in modo da visualizzare il potenziale movimento anche nella più semplice delle situazioni.
Se è importante, sto cercando di fare questo in javascript, ma ad essere onesti penso che il mio fallimento qui è un fallimento di concettualizzare correttamente -. Non un fallimento nella comprensione del linguaggio
Aggiornamento - sto aggiungendo al primo turno del codice scritto, dopo le risposte sotto sono state pubblicate. Ho pensato che potrebbe essere utile per le persone in una situazione simile come me per vedere il codice
E 'sciatta e funziona solo per un elemento posto sulla scheda fino ad ora, ma almeno la funzione check_allowable_moves() lavora per questa corsa iniziale. Per quelli di voi chiedendo perché diavolo sto creando quegli oggetti strani alfanumerici piuttosto che utilizzare l'asse x numerica e l'asse y - è perché un id in HTML non può iniziare con un numero. In realtà fingendo I potrebbero i numeri utilizzare per avviare ids aiutato molto a rendere il senso della funzionalità ei concetti descritti dalle fantastiche risposte che ho ricevuto.
<!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>
Soluzione
Supponiamo piece p è in posizione x, y e può muoversi n caselle di distanza in posizione x2, y2. Ciò significa che la somma delle differenze assolute tra (x - x2) e. (Y - y2) può essere non maggiore di n
Se avete intenzione di mostrare che le piazze possono essere spostati (piuttosto che prendere gli ingressi X2 e Y2), penso che sarebbe meglio per un ciclo su tutte le posizioni in un quadrato attorno al pezzo. Cioè ...
for (x - n TO x + n):
for (y - n TO x + n):
if (abs(x - x2) + abs(y - y2) <= n):
mark as okay.
Questa risposta presuppone pezzi possono muovere solo a caselle adiacenti e non in diagonale.
Edit: Se si desidera che il movimento in diagonale, e si muove lungo un costo diagonale tanto quanto lo spostamento orizzontale o in verticale, allora il problema è in realtà molto più facile - il pezzo p può muoversi tra gli intervalli di (x - n, x + n) e (y -. n, y + n)
La risposta diventa molto più complesso se un diagonale non costa tanto quanto un movimento orizzontale + verticale (ad esempio, se i costi diagonali 1,5, mentre h costi / v 1).
Altri suggerimenti
In tali problemi generali comportano una griglia ragionevolmente limitato di posti si può eventualmente raggiungere. Prendere una struttura di dati della dimensione della griglia e la cui elementi può contenere il numero dei rimanenti punti movimento con sufficiente precisione.
inizializzare la rete ad un valore non-visitato. Ciò non deve essere nell'intervallo di zero alla massima velocità possibile spostamento. Un valore negativo è l'ideale.
Inizializzare la posizione di partenza per il numero di mosse rimanenti.
A questo punto ci sono tre possibili approcci:
1) Riscansiona l'intera griglia ogni passo. Semplice ma più lento. La terminazione è quando non ci sono punti di cedere una mossa legale.
2) Punti di memorizzare su una pila. Più veloce di 1 #, ma ancora non il migliore. La terminazione è quando la pila è vuota.
3) Punti di memorizzare in una coda. Questo è il migliore. La terminazione è quando la coda è vuota.
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
Si noti che con l'approccio basato su stack si avrà sempre alcuni casi in cui si finisce per buttare fuori i vecchi calcoli e facendo di nuovo. Un approccio basato su coda avrà questo accada solo se ci sono casi in cui andando in giro cattivo terreno è più economico di andare attraverso di essa.
Controllare la condizione di terminazione solo alla fine del ciclo, oppure terminare quando ObtainPoint tenta di utilizzare una coda vuota o una pila. Un vuoto di coda / pila dopo ObtainPoint non significa che si è fatto!
(Si noti che è una notevole espansione risposta di Ian.)
Questo è puramente a livello concettuale, ma provate questa logica:
-
Prendere tutte le posizioni possibili ad un passo dal vostro punto di partenza e metterle sulla pila (movimenti presi = 0)
-
pop dallo stack e ripetere, utilizzando tale nuova coordinata come nuovo punto di partenza. (movimenti presi = 1). Dovrete garantire che non mettere alcun coordinate duplicati sullo stack
-
Ripeti 2 fino a quando hai esaurito tutte le mosse disponibili del tuo pezzo.
I non può essere spiegare questo al bene, fatemi sapere se avete domande su quello che sto cercando di dire.
È possibile utilizzare il metodo di cui sopra, ma usare la ricorsione invece.
Il ricorsione "profondità" è la distanza di movimento.
Break out quando la profondità> movimento.
Ogni iterazione deve restituire un vettore di spazi e aggiungere la propria posizione.
Rimuovi duplicati
