Archief - C# pathfinding

Gegroet,

Ik ben bezig met het creëren van een "tower defence" in C#.
Met behulp van een 2 dimensionale array heb ik een mijn speelveld gecreëerd.
Als een bepaalde positie 0 is wordt er een groen vierkant getekend, anders wordt er een blauw vierkant getekend. ( Dit vormt dan het pad. ) Nu vroeg ik mij hoe ik ervoor kan zorgen dat een bepaald object dit pad kan volgen zonder 1 bepaalde weg te "hard coden".

Alvast bedankt.

code
-----

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 towerdefense
{
class Level prite
{

public Level(PictureBox picturebox)
{

}

int[,] map =


{

{0,0,1,0,0,0,0,0,0,0},

{0,0,1,0,0,0,0,0,0,0},

{0,0,1,1,1,1,1,1,0,0},

{0,0,0,0,0,0,0,1,0,0},

{0,0,0,0,0,0,0,1,0,0},

{0,0,1,1,1,1,1,1,0,0},

{0,0,1,0,0,0,0,0,0,0},

{0,0,1,0,0,0,0,0,0,0},

{0,0,1,0,0,0,0,0,0,0},

{0,0,1,1,1,1,1,1,1,1}

};
public void Display(Graphics drawArea)
{


for (int i = 0; i <= 9; i++)
{
for (int y = 0; y <= 9; y++)
{
int textureIndex;
textureIndex = map[y,i];
if ( textureIndex == 0)
{

SolidBrush brush = new SolidBrush(Color.Green);
drawArea.FillRectangle(brush, i * 50, y * 50 , 50, 50);

}
else
{
SolidBrush brush = new SolidBrush(Color.Blue);
drawArea.FillRectangle(brush, i * 50, y * 50, 50, 50);
}
}
}
}


}
}

Ik had vorig jaar het vak Algoritmen en Architectuur van Computergames waarbij ik oa de AI geïmplementeerd had

Is redelijk easy te doen. Hier hebt ge slides waarin het zowat wordt uitgelegd:
* http://didactiekinf.uhasselt.be/aac/lesmateriaal/AI.pdf
* http://didactiekinf.uhasselt.be/aac/uploads/Main/ai-2.pdf

Denk dat vooral de eerste interessant is voor u A*

Wat ge basically doet is vanaf uw punt (waar ge staat) kijken naar alle veldjes rond u. En dan voor die veldjes bepaalt ge of die al dan niet toegankelijk zijn, als da nie zo is negeert ge da.

Als die wel toegankelijk zijn, houdt ge die ergens bij en kijkt ge voor elk van die veldjes hoever dat die van het eindpunt afliggen. Ge moet da inschatten, gokken, dus gwn euclidische afstand ofzo (ookal zitten daar misschien objecten in de weg).

Dan pakt ge het veldje wat het dichtstbij lag en daarvoor doet ge hetzelfde. Als ge ooit geen opties meer hebt of alle opties zijn slecht, dan gaat ge backtracken en andere veldjes proberen. De route die uiteindelijk krijgt zal de kortste zijn in bepaalde uitzonderingen na.

Het leuke hier is dat ge bepaalde veldjes een moeilijkheids-waarde kunt meegeven (bv ondiep water vs gras, ondiep water krijgt een hogere waarde dan gras, waardoor gras soms de gewenste route zal vormen, hoewel die misschien om moet lopen dan).

Edit: hier ziet ge hoe da in ons spel toegepast werd (in 3D wel): http://home.scarlet.be/gertnelissen/AACG/Screens/astar.png, die bollekes zijn de waypoints van de AI. Ge ziet dat die netjes rond da huis gaat enz

Hier is onze game trouwens http://didactiekinf.uhasselt.be/aac/index.php?n=AACG0910Groep2.Gallery

de vijand begint bijvoorbeeld op positie (0,0)
=> kijken naar omliggende buren voor een 1 (let op boundries)
buur gevonden op 0,1 en verschillend van vorige positie
=>
vorigePos = 0,0
huidigePos = 0,1



lectuur over 'echte' pathfinding

Amit&#8217;s A* Pages

Gurdt zei:

...

Klik om te vergroten...

Een mug neerschieten met een kanon...

Anyway, floyd warshall does the trick: Floyd (zie ook vooral naar path reconstruction). Je kan ook nog Dijkstra toepassen: Dijkstra's algorithm - Wikipedia, the free encyclopedia, maar floyd warshall is iets meer straightforward te programmeren en te begrijpen naar mijn mening.

Cycloon zei:

Een mug neerschieten met een kanon...

Anyway, floyd warshall does the trick: Floyd (zie ook vooral naar path reconstruction). Je kan ook nog Dijkstra toepassen: Dijkstra's algorithm - Wikipedia, the free encyclopedia, maar floyd warshall is iets meer straightforward te programmeren en te begrijpen naar mijn mening.

Klik om te vergroten...

Gij moet toch ook altijd kunnen kakken he...

Da wa ik geef wordt toegepast in vele games dus ge moet nie onnozel komen doen en zeggen dat da overdreven is. Wa is daar trouwens overdreven aan? Te complex? Nie efficiënt genoeg? Uwen Dijkstra en Floyd doen in essentie zelfs hetzelfde als A*. Floyd is zelfs minder efficient...

Nuja, gij gaat da waarschijnlijk wel beter weten he

Edit: ik zou wel ens willen weten wa voor iemand gij in het echt zijt.
Ik heb hier nog geen ENKEL subject gezien waarover gij NIE aan het kakken waart. Als iedereen zo fout is volgens u, waarom zijt ge dan nie CIO in een of ander dik bedrijf?

Gurdt zei:

Big rant...

Klik om te vergroten...

Nee serieus, waarom voelt gij u weer aangevallen?

• De TS is duidelijk iemand met weinig ervaring
• Ik antwoord gewoon to the point
• Niemand is geïnteresseerd in het feit dat je een cursus AI hebt gehad, laat dat dan ook achterwege
• Heb ik over iemand gezegd dat die fout is?

Cycloon zei:

Nee serieus, waarom voelt gij u weer aangevallen?

• De TS is duidelijk iemand met weinig ervaring
• Ik antwoord gewoon to the point
• Niemand is geïnteresseerd in het feit dat je een cursus AI hebt gehad, laat dat dan ook achterwege
• Heb ik over iemand gezegd dat die fout is?

Klik om te vergroten...

• Gij zegt: schiet een mug dood met een kanon, waarmee ge in mijn ogen wilt zeggen dat mijn methode overkill is
• Mijn methode is helemaal geen overkill
• Als de TS weinig ervaring heeft zal hij geen AI gaan implementeren
• Mijn aangereikte methode is zelfs door dwazeriken te begrijpen
• Ik geef gewoon aan vanwaar ik het geleerd heb, het is trouwens helemaal geen cursus AI. Ik laat dat niet achterwege want ik geef de TS slides waarin alles piekfijn uitgelegd wordt. Ik schep een beeld rond die slides, die ik van school heb. Als gij da nie relevant vindt, bol het dan af en reageer daar nie op.
• Fout is mijn methode sowieso niet.
• Als ge zo graag to the point wilt zijn, laat dan uw reactie op mij achterwege.
• Gij zit gewoonweg in ELKE thread die informatica-gerelateerd is te schijten op alles en iedereen. Ik ben u nickname gewoonweg beu. Ik heb al vaak getwijfeld om u op een negeerlijst te zetten maar dan mis ik wellicht enkele kromme meningen en dat vind ik veel te plezant.

Jong bolletaf serieus.

Ik denk dat pieta hier goed zit. De doelstelling is niet om het kortste pad te vinden, maar om gewoon vijanden langs het pad te laten lopen. Als ik mij tenminste niet vergis van game. Dan kan je gewoon naar de buren kijken naar waar je kunt stappen (en je negeert de buur vanwaar je kwam) en daar stap je dan naartoe. Als er maar 1 uniek pad is dan is het gemakkelijk: dan is er telkens maar 1 zo'n buur. Als er splitsingen zijn dan laat je de vijanden willekeurig een buur kiezen om naartoe te stappen.

Als er lussen in de paden zitten dan wordt het wat lastiger. Dan zul je ofwel meer dan alleen de vorige buur moeten onthouden ofwel een andere aanpak moeten gebruiken.

Dat werkt inderdaad alleen maar als er 1 uniek pad is. En dan is dat nog steeds hardcoded TS?

Cycloon zei:

Een mug neerschieten met een kanon...

Klik om te vergroten...

Ik veronderstel dat jij ook een bubble sort boven een quicksort prefereert?

Nee, serieus: A* all the way! Op google moet je wel genoeg C# implementaties van A* kunnen vinden.

Gurdt zei:

Dat werkt inderdaad alleen maar als er 1 uniek pad is. En dan is dat nog steeds hardcoded TS?

Klik om te vergroten...

veel tower defence spellen hebben ook gewoon vaste mappen, en zelfs als er een splitsing wordt er soms vast gezegd welke weg ze moeten moeten volgen.

tis ook een beginner, iemand die nog nie zoveel ervaring heeft in een logische oplossing te zoeken. een simpel beginnen en een snel een werkend spel te hebben is beter voor de goesting dan een week zitten proberen voor een 'betere' oplossing. als de ts zn programma gereed is kan hij nog vb random maps maken en pathfinding toepassen ( en ook snapt en nie gewoon wa code c/p'en)

edit: tis nie dat uw post afraad he ook pdf's en de projecten zijn eens tof om te zien!

kwitters zei:

Ik veronderstel dat jij ook een bubble sort boven een quicksort prefereert?

Klik om te vergroten...

Nee, ik zou shell sort beginnen uitleggen, powerpoints geven over verschillende interessante reeksen om te gebruiken én een voorbeeld geven waar ik het zelf al heb gebruikt

pieta zei:

veel tower defence spellen hebben ook gewoon vaste mappen, en zelfs als er een splitsing wordt er soms vast gezegd welke weg ze moeten moeten volgen.

tis ook een beginner, iemand die nog nie zoveel ervaring heeft in een logische oplossing te zoeken. een simpel beginnen en een snel een werkend spel te hebben is beter voor de goesting dan een week zitten proberen voor een 'betere' oplossing. als de ts zn programma gereed is kan hij nog vb random maps maken en pathfinding toepassen ( en ook snapt en nie gewoon wa code c/p'en)

edit: tis nie dat uw post afraad he ook pdf's en de projecten zijn eens tof om te zien!

Klik om te vergroten...

Toch iemand die het begrijpt

Nou, ik vind dat hele objectgeorienteerd programmeren overroepen.

En java is beter dan C++.

(en testen is voor mensen die tijd teveel hebben)

Schrijft gij dan maar eens software die moet kunnen evolueren in niet OO :doc:

Aan de OP: vindt u een library voor A* in C#. Bij zo'n implementaties is alles al uitgewerkt, vaak moet gij alleen nog een interface voorzien voor "de situatie van de grid" en voor de "burenrelatie". Dat wordt wel duidelijk als je met zo'n library begint.

A-Star (A*) Implementation in C# (Path Finding, PathFinder) - CodeGuru

Als ge door die link eens doorleest en op het einde wa met die source prult komt da in orde.

Is het eigenlijk iemand al opgevallen dat de OP nog niet gereageerd heeft?

Krueger zei:

Is het eigenlijk iemand al opgevallen dat de OP nog niet gereageerd heeft?

Klik om te vergroten...

Nou, dat was me nog niet opgevallen, maar nu je het zegt...

Cycloon zei:

Nee, ik zou shell sort beginnen uitleggen, powerpoints geven over verschillende interessante reeksen om te gebruiken én een voorbeeld geven waar ik het zelf al heb gebruikt

Klik om te vergroten...

Exactly my point: Jij zou enorm veel tijd besteden aan een inferieur algoritme. Als het over C# gaat zou ik maar 1 ding zeggen: .Sort() method. En rara, dat is een quick sort. 1 second uitleg, 2 seconden om te "implementeren", en sneller dan eender welk ander ding waarmee gij gaat afkomen.

Zelfde met A*. Jij zou iets zelf geschreven proberen wat niet echt fatsoenlijk gaat werken. Ik zou gewoon een A* implementatie van het net plukken en dat gebruiken. Sneller in implementatie en sneller in uitvoer.

Uw implementatiekunsten zijn blijkbaar even efficient als uw algoritmes.

kwitters zei:

Exactly my point: Jij zou enorm veel tijd besteden aan een inferieur algoritme. Als het over C# gaat zou ik maar 1 ding zeggen: .Sort() method. En rara, dat is een quick sort. 1 second uitleg, 2 seconden om te "implementeren", en sneller dan eender welk ander ding waarmee gij gaat afkomen.

Zelfde met A*. Jij zou iets zelf geschreven proberen wat niet echt fatsoenlijk gaat werken. Ik zou gewoon een A* implementatie van het net plukken en dat gebruiken. Sneller in implementatie en sneller in uitvoer.

Uw implementatiekunsten zijn blijkbaar even efficient als uw algoritmes.

Klik om te vergroten...

Ik geef hem nochtans gelijk: overkill en bijlange niet nodig. En helemaal niet gemakkelijk om te begrijpen en te implementeren voor iemand die pas begonnen is met programmeren zelfs met een library.

"sneller dan eender welk ander ding waarmee gij gaat afkomen."
Radix sort.