Diffusion vs Dijkstra

Size	Parallel Diffusion (ms)	Sequential Diffusion (ms)	Sequential Dijkstra (ms)
32x32	0.19	0.7	1
64x64	0.51	3.7	3.8
128x128	2.88	62.01	16.2
256x256	32.91	1050.66	68.01
512x512	498.59	16949.22	277.07
1024x1024	9024.56	280763.5	1146.38
2048x2048	133185.1	4598425	4954.72

Time to fill varying grid sizes.

Map	Parallel	Sequential
32x32	31	31
64x64	75	68
128x128	261	224
256x256	1026	866
512x512	4175	3507
1024x1024	17176	14382
2048x2048	65091	59256

Iterations to fill all tiles with zero value

Map	Centre as goal	Bottom right as goal
32x32	16	31
64x64	32	75
128x128	76	261
256x256	262	1026
512x512	1018	4175
1024x1024	4089	17176
2048x2048	16589	65091

Iterations for parallel diffusion for different goals

Map	Centre as goal (ms)	Bottom right as goal (ms)
32x32	0.10	0.19
64x64	0.22	0.51
128x128	0.85	2.88
256x256	8.45	32.91
512x512	121.94	498.59
1024x1024	2158.84	9024.56
2048x2048	30841.5	133185.1

Time to find paths for different goal tiles parallel diffusion

Map	Centre as goal (ms)	Bottom right as goal (ms)
32x32	0.90	1
64x64	3.8	3.8
128x128	16.1	16.2
256x256	66.31	68.01
512x512	277.27	277.07
1024x1024	1109.87	1146.38
2048x2048	4594.73	4954.72

Time for dijkstra to find paths for different goals

Map	Centre as goal	Bottom right as goal
32x32	0.17	0.25
64x64	0.66	0.77
128x128	2.78	3.38
256x256	11.92	13.20
512x512	47.43	51.05
1024x1024	194.66	210.84
2048x2048	1097.17	1188.43

Time for A* to find paths for different goals

Map	2^10	2^20	2^50	2^100
32x32	16	16	16	16
64x64	32	32	32	32
128x128	76	73	66	64
256x256	262	245	207	170
512x512	1018	945	779	608
1024x1024	4089	3783	3091	2376
2048x2048	16589	15317	12459	9516

Number of iterations for parallel diffusion to find the goal at the centre when the goal value is different

Map	2^10 (ms)	2^20 (ms)	2^50 (ms)	2^100 (ms)
32x32	0.1	0.1	0.1	0.1
64x64	0.22	0.22	0.22	0.22
128x128	0.85	0.82	0.74	0.71
256x256	8.45	7.9	6.68	5.49
512x512	121.94	112.967	93.21	72.75
1024x1024	2158.84	1990.4	1623.91	1248.21
2048x2048	30841.5	28490.8	23215.2	17686.3

Time for parallel diffusion to find goal at the centre when the goal value is different