Benchmark unserer Wegsuchalgorithmen - Earthproject Forum

Du bist nicht angemeldet.

Benchmark unserer Wegsuchalgorithmen

Tirus

Entwickler

Beiträge: 31

1

16 May 2014, 20:53

Benchmark unserer Wegsuchalgorithmen

Vorneweg: Unsere Wegsuche ist noch lange nicht fertig.

Wir haben zur Zeit 3 verschiedene Algorithmen für die Wegsuche implementiert,
wobei einer (die Breitensuche) nur als Referenz dienen soll.

Ich habe nun einen kleinen Benchmark geschrieben der auf der aktuellen Testkarte diverse Wegsuchen starten und die Zeit misst, wie lange jede Implementierung dafür benötigt.

Die Zeitangaben sind dabei in Mikrosekunden angegeben.
(Code aus Revision 174)

Quellcode


Teste PathFinder Algorithmen (je 10 durchlaeufe)
Zeitangaben in us (Mikrosekunden)
Test: Kurze Suche ohne Hindernis (10, 10) -> (20, 10)
min	max	avg	fields	found
771	2086	1129	10	1	(AStar)
76	545	127	10	1	(Breitensuche)
10	14	10	10	1	(Jump Point Search)
Test: Horizontal ueber ganze Karte (ohne Hindernis) (20, 500) -> (1015, 500)
min	max	avg	fields	found
1951	2136	2019	995	1	(AStar)
32217	33344	32620	995	1	(Breitensuche)
2240	2775	2423	995	1	(Jump Point Search)
Test: Diagonal ueber ganze Karte (1, 1) -> (1021, 1021)
min	max	avg	fields	found
14187	16975	15426	1205	1	(AStar)
31588	35894	32851	1205	1	(Breitensuche)
10444	11734	10712	1205	1	(Jump Point Search)
Test: GroundHill Diagonal (148, 20) -> (302, 238)
min	max	avg	fields	found
4438	4842	4574	221	1	(AStar)
1303	1407	1330	221	1	(Breitensuche)
1001	1063	1015	221	1	(Jump Point Search)
Test: GroundHill Vertikal (225, 24) -> (225, 234)
min	max	avg	fields	found
3213	3449	3357	210	1	(AStar)
1287	1842	1367	210	1	(Breitensuche)
310	360	319	210	1	(Jump Point Search)
Test: Berg in Taal (links oben) (10, 20) -> (25, 56)
min	max	avg	fields	found
2375	2801	2518	97	1	(AStar)
233	452	257	97	1	(Breitensuche)
158	194	163	97	1	(Jump Point Search)
Test: Spiralberg (rechts oben) von unten nach oben (772, 115) -> (897, 127)
min	max	avg	fields	found
104692	114520	109974	624	1	(AStar)
20210	23561	21027	624	1	(Breitensuche)
8379	10740	8711	624	1	(Jump Point Search)
Test: Durch Labyrinth (rechts oben) (790, 227) -> (963, 430)
min	max	avg	fields	found
11236	12436	11495	333	1	(AStar)
7294	7509	7365	333	1	(Breitensuche)
1829	6582	2368	333	1	(Jump Point Search)
Test: Durch Spirale ins innere (rechts oben) (774, 433) -> (718, 371)
min	max	avg	fields	found
433606	664478	603734	1303	1	(AStar)
33941	35815	34769	1303	1	(Breitensuche)
20101	21877	20692	1303	1	(Jump Point Search)
Test: Aus Spirale auf Spiralberg (719, 371) -> (903, 141)
min	max	avg	fields	found
351672	365610	358134	2538	1	(AStar)
33793	38618	34743	2538	1	(Breitensuche)
18513	19899	18855	2538	1	(Jump Point Search)
Test: Von Spiralberg in Spirale (903, 141) -> (719, 371)
min	max	avg	fields	found
679243	977220	915371	2538	1	(AStar)
34102	38365	35190	2538	1	(Breitensuche)
35631	39925	36479	2538	1	(Jump Point Search)
Test: Karte "Teufelsschucht" einmal durch (links unten) (300, 957) -> (399, 983)
min	max	avg	fields	found
22667	24372	23217	404	1	(AStar)
6891	7468	7045	404	1	(Breitensuche)
6689	9443	7010	404	1	(Jump Point Search)
Test: Felder nahe aber grosser Umweg (small Worst Case) (22, 957) -> (23, 954)
min	max	avg	fields	found
14511	16489	14972	325	1	(AStar)
3956	4142	4013	325	1	(Breitensuche)
1844	2013	1892	325	1	(Jump Point Search)
Test: Suche ohne mgl. Weg (beschraenkt) (26, 20) -> (22, 20)
min	max	avg	fields	found
672	1238	1007	0	0	(AStar)
70	327	97	0	0	(Breitensuche)
0	4	1	0	0	(Jump Point Search)
Test: Suche ohne mgl. Weg (viel Fl.) (Worst Case!) (22, 20) -> (26, 20)
min	max	avg	fields	found
860531	968811	944043	0	0	(AStar)
34157	34981	34494	0	0	(Breitensuche)
19585	22403	20275	0	0	(Jump Point Search)


Zum System:
Dies lief auf meinem Rechner mit eine Intel Core2Duo E8500 CPU auf 3,33Ghz.

Compiliert als Release mit -O3.

Tirus

Entwickler

Beiträge: 31

2

24 May 2014, 23:25

Mal wieder ein aktueller Benchmark mit Revision 187.

In der Zwischenzeit wurde die AStar und die Breitensuchen Implementierung verbessert.
In beiden wurde hauptsächlich die Speichernutzung optimiert.

Quellcode


Teste PathFinder Algorithmen (je 10 durchlaeufe)
Zeitangaben in us (Mikrosekunden)
Test: Kurze Suche ohne Hindernis (10, 10) -> (20, 10)
min	max	avg	fields	found
2206	2565	2375	10	1	(AStar)
71	558	120	10	1	(Breitensuche)
10	18	11	10	1	(Jump Point Search)
Test: Horizontal ueber ganze Karte (ohne Hindernis) (20, 500) -> (1015, 500)
min	max	avg	fields	found
2131	3128	2875	995	1	(AStar)
15006	16698	15326	995	1	(Breitensuche)
2231	2278	2252	995	1	(Jump Point Search)
Test: Diagonal ueber ganze Karte (1, 1) -> (1021, 1021)
min	max	avg	fields	found
7973	11264	8844	1205	1	(AStar)
14570	15401	14719	1205	1	(Breitensuche)
10324	11481	10483	1205	1	(Jump Point Search)
Test: GroundHill Diagonal (148, 20) -> (302, 238)
min	max	avg	fields	found
2807	3712	3513	221	1	(AStar)
685	1003	718	221	1	(Breitensuche)
1017	1080	1033	221	1	(Jump Point Search)
Test: GroundHill Vertikal (225, 24) -> (225, 234)
min	max	avg	fields	found
2565	3554	3329	210	1	(AStar)
672	990	707	210	1	(Breitensuche)
313	323	314	210	1	(Jump Point Search)
Test: Berg in Taal (links oben) (10, 20) -> (25, 56)
min	max	avg	fields	found
2408	3341	3150	97	1	(AStar)
150	411	181	97	1	(Breitensuche)
169	181	172	97	1	(Jump Point Search)
Test: Spiralberg (rechts oben) von unten nach oben (772, 115) -> (897, 127)
min	max	avg	fields	found
57457	61229	58543	624	1	(AStar)
9296	9976	9388	624	1	(Breitensuche)
8229	11705	8634	624	1	(Jump Point Search)
Test: Durch Labyrinth (rechts oben) (790, 227) -> (963, 430)
min	max	avg	fields	found
7687	10717	8354	333	1	(AStar)
3568	4052	3629	333	1	(Breitensuche)
1785	1961	1821	333	1	(Jump Point Search)
Test: Durch Spirale ins innere (rechts oben) (774, 433) -> (718, 371)
min	max	avg	fields	found
229928	233830	231449	1303	1	(AStar)
15744	18199	16116	1303	1	(Breitensuche)
19852	20400	19946	1303	1	(Jump Point Search)
Test: Aus Spirale auf Spiralberg (719, 371) -> (903, 141)
min	max	avg	fields	found
172263	178355	174083	2538	1	(AStar)
15811	18187	16156	2538	1	(Breitensuche)
18185	22594	18714	2538	1	(Jump Point Search)
Test: Von Spiralberg in Spirale (903, 141) -> (719, 371)
min	max	avg	fields	found
322013	325789	323374	2538	1	(AStar)
15747	16759	15918	2538	1	(Breitensuche)
35089	43658	36064	2538	1	(Jump Point Search)
Test: Karte "Teufelsschucht" einmal durch (links unten) (300, 957) -> (399, 983)
min	max	avg	fields	found
14091	15779	14769	404	1	(AStar)
3305	3516	3346	404	1	(Breitensuche)
6587	6689	6634	404	1	(Jump Point Search)
Test: Felder nahe aber grosser Umweg (small Worst Case) (22, 957) -> (23, 954)
min	max	avg	fields	found
10501	12227	11133	325	1	(AStar)
1889	2356	1940	325	1	(Breitensuche)
1837	1929	1858	325	1	(Jump Point Search)
Test: Suche ohne mgl. Weg (beschraenkt) (26, 20) -> (22, 20)
min	max	avg	fields	found
1544	2392	2257	0	0	(AStar)
65	316	90	0	0	(Breitensuche)
0	4	1	0	0	(Jump Point Search)
Test: Suche ohne mgl. Weg (viel Fl.) (Worst Case!) (22, 20) -> (26, 20)
min	max	avg	fields	found
384001	388460	386233	0	0	(AStar)
15693	17628	16027	0	0	(Breitensuche)
19360	19544	19441	0	0	(Jump Point Search)


Wie man sehen kann braucht die AStar implementierung "nur noch" etwa 1/3 der vorherigen Zeit, wobei diese jedoch immernoch deutlich zu langsam ist.
Die Breitensuche benötigt etwas weniger als die hälfte wie vorher, und ist damit in ein paar Fälle nun die schnellste Lösung.
An der JPS Implementierung wurde bisher nichts geändert, die Zeitlichen unterschiede sind normalen Messschwankungen zuzurechnen.

MSC

Teh Atmin!

Beiträge: 97

3

26 May 2014, 14:47

Ein Ansatz wäre auch, dass die Einheiten sich voerst nach Luflinie in Bewegung setzen und die Wegfingund als Nebenprozess geschieht.
Sobald der Weg ermittelt ist, Fahren die Einheiten dann danach.

Eine Ausnahme muss bei sehr kleinen Umkreisbewegungen gemacht werden: wenn man eine beschädigte Einheit an der Front nach hinten setzen möchte, muss diese den Weg schnell bewerkstelligen.
Das Micromanagement darf nicht durch Wegfindungen behindert werden.


Zu überlegen ist auch der Fall, wenn kein Weg gefunden werden kann, wie dann das nächst mögliche Ziel bestimmt wird.
Sicherlich kannst du nicht von X Koordinaten im Umkreis testen, ob die Einheiten bis dahin gelangen können.


Wäre es eig. mögich, dass eine Map im Vorraus analysiert wird, welche Wege möglich sind, und die Wegfindung darauf zuggreifen kann?
Als Beispiel abgeschlossene Bereiche, z.B. passierbarer Berggipfel die aber keine Verbindung zu den Restlichen Wegen auf der Map hat.
Diese Fläche und unpassierbare Bereiche könnte dann bei der Wegfindung von vorn herein Ausgeschlossen werden.
Bzw. die zusammenhängenden Flächen werden in Gruppen aufgeteilt, nur wenn die Einheit auf der gleichen Flächengruppe wie das Ziel liegt, wird dies direkt berechnet. (ich bau mal ein Beispiel Bild heute Abend).
Erst wenn diese Fläche mit den restlichen Flächen verbunden sind (weil Gelände geebnet, Tunneleingang, Teleporter...), werden diese wieder berücksichtigt. Dies könnte ja auch durch nebenprozesse geschehen.
Vorteil: die Wegfindung für alternative Ziele in der Umgebung könnte dadurch deutlich entlastet werden, da die Mögliche Anzahl der alternativen sinkt und diese Ziele bekannt und berechenbar sind.


Ein weiter Ansatz wäre (aber bissel Unbequem für die Spieler), dass Einheiten nur erkundete Bereiche auch befahren können.

MSC

Teh Atmin!

Beiträge: 97

4

26 May 2014, 18:35

Test bei mir.

Quellcode

Laden der Map erfolgreich
Teste PathFinder Algorithmen (je 10 durchlaeufe)
Zeitangaben in us (Mikrosekunden)
Test: Kurze Suche ohne Hindernis (10, 10) -> (20, 10)
min	max	avg	fields	found
973	1238	1034	10	1	(AStar)
35	197	51	10	1	(Breitensuche)
6	12	8	10	1	(Jump Point Search)
Test: Horizontal ueber ganze Karte (ohne Hindernis) (20, 500) -> (1015, 500)
min	max	avg	fields	found
1324	1448	1357	995	1	(AStar)
10553	11055	10837	995	1	(Breitensuche)
1682	1803	1745	995	1	(Jump Point Search)
Test: Diagonal ueber ganze Karte (1, 1) -> (1021, 1021)
min	max	avg	fields	found
5290	5762	5585	1205	1	(AStar)
9991	11192	10394	1205	1	(Breitensuche)
7876	8375	8108	1205	1	(Jump Point Search)
Test: GroundHill Diagonal (148, 20) -> (302, 238)
min	max	avg	fields	found
1881	2146	1972	221	1	(AStar)
452	547	475	221	1	(Breitensuche)
726	793	751	221	1	(Jump Point Search)
Test: GroundHill Vertikal (225, 24) -> (225, 234)
min	max	avg	fields	found
1722	1833	1776	210	1	(AStar)
453	487	460	210	1	(Breitensuche)
217	252	230	210	1	(Jump Point Search)
Test: Berg in Taal (links oben) (10, 20) -> (25, 56)
min	max	avg	fields	found
1596	1853	1680	97	1	(AStar)
86	117	93	97	1	(Breitensuche)
117	141	123	97	1	(Jump Point Search)
Test: Spiralberg (rechts oben) von unten nach oben (772, 115) -> (897, 127)
min	max	avg	fields	found
38088	38978	38624	624	1	(AStar)
6362	6887	6610	624	1	(Breitensuche)
6442	7973	6943	624	1	(Jump Point Search)
Test: Durch Labyrinth (rechts oben) (790, 227) -> (963, 430)
min	max	avg	fields	found
5047	5502	5242	333	1	(AStar)
2353	2775	2494	333	1	(Breitensuche)
1444	1578	1487	333	1	(Jump Point Search)
Test: Durch Spirale ins innere (rechts oben) (774, 433) -> (718, 371)
min	max	avg	fields	found
155321	160397	157170	1303	1	(AStar)
11137	12558	11528	1303	1	(Breitensuche)
15472	16412	15931	1303	1	(Jump Point Search)
Test: Aus Spirale auf Spiralberg (719, 371) -> (903, 141)
min	max	avg	fields	found
114660	119781	116732	2538	1	(AStar)
10987	11741	11414	2538	1	(Breitensuche)
14322	15119	14662	2538	1	(Jump Point Search)
Test: Von Spiralberg in Spirale (903, 141) -> (719, 371)
min	max	avg	fields	found
212538	218388	215373	2538	1	(AStar)
10778	11930	11107	2538	1	(Breitensuche)
27046	28838	27610	2538	1	(Jump Point Search)
Test: Karte "Teufelsschucht" einmal durch (links unten) (300, 957) -> (399, 983)
min	max	avg	fields	found
9291	9879	9487	404	1	(AStar)
2267	2628	2346	404	1	(Breitensuche)
5114	5712	5405	404	1	(Jump Point Search)
Test: Felder nahe aber grosser Umweg (small Worst Case) (22, 957) -> (23, 954)
min	max	avg	fields	found
6554	6815	6657	325	1	(AStar)
1259	1339	1292	325	1	(Breitensuche)
1505	1937	1598	325	1	(Jump Point Search)
Test: Suche ohne mgl. Weg (beschraenkt) (26, 20) -> (22, 20)
min	max	avg	fields	found
984	1073	1021	0	0	(AStar)
31	49	34	0	0	(Breitensuche)
0	3	0	0	0	(Jump Point Search)
Test: Suche ohne mgl. Weg (viel Fl.) (Worst Case!) (22, 20) -> (26, 20)
min	max	avg	fields	found
249762	254392	252652	0	0	(AStar)
10996	12267	11354	0	0	(Breitensuche)
14877	15806	15215	0	0	(Jump Point Search)