ui/src/lib/graph.ts · astrolabe

git.iko.soy/astrolabe

422 lines 13 kB history raw

1import Graph from 'graphology';

2import * as colors from './colors';

4const example = '[0[3216291:t;9219219;4608:s[156546;1612196;219621:~;321965149:4608;]1280[4289594624;4278191360;426672256;4260168960;4260824320;4246668544;4246144256;4253746432;4235396352;4230415616;4225697024;4227007744;4219667712;4222616832;4224648448;4214490368;4215997696;4219143424;4237296896;]]]'

6export interface ChartPoint {

7 patp: string,

8 dominion: ('l1' | 'l2' | 'spawn'),

9 picked: boolean,

10 pickedChildren?: boolean,

11 pickedSponsees?: boolean,

12 sponsor?: string,

13 parent?: string,

14 children?: ChartPoint[],

15 sponsees?: ChartPoint[],

16}

18interface ChartSubs {

19 children: ChartPoint[],

20 sponsees: ChartPoint[],

21}

23class ChartDataParser {

24 filter: Set<string>;

26 constructor(filter: Set<string>) {

27 this.filter = filter;

28 }

30 parseMetaString(metaString: string): ChartPoint {

31 let idString, subMetaString = '';

32 const colIndex = metaString.indexOf(':');

33 if (colIndex === -1) {

34 idString = metaString;

35 } else {

36 idString = metaString.slice(0, colIndex);

37 subMetaString = metaString.slice(colIndex + 1);

38 }

39 const patp = '~' + idString;

40 const meta: ChartPoint = {

41 patp,

42 picked: !this.filter ? true : (this.filter.has(patp)),

43 dominion: 'l1',

44 }

45 if (subMetaString) {

46 const firstChar = subMetaString[0];

47 if (firstChar === 't') {

48 meta.dominion = 'l2';

49 subMetaString = subMetaString.slice(1);

50 } else if (firstChar === 's') {

51 meta.dominion = 'spawn';

52 subMetaString = subMetaString.slice(1);

53 }

54 if (subMetaString) {

55 if (subMetaString[0] === '~') {

56 meta.sponsor = null;

57 } else {

58 let [sponsor, parent] = subMetaString.slice(1).split('!');

59 meta.sponsor = '~' + sponsor;

60 meta.parent = '~' + parent;

61 }

62 }

63 }

64 return meta;

65 }

67 extractMeta(data: string): [ChartPoint, string] {

68 const index = data.search(/[[;]/);

69 if (index === -1) {

70 throw new Error(`No point meta present in ${data}`);

71 }

72 const metaString = data.slice(0, index);

73 data = data.slice(index);

74 return [this.parseMetaString(metaString), data];

75 }

77 extractChildren(data: string, sup: string = undefined): [ChartSubs, string] {

78 if (data[0] === ';')

79 return [{

80 children: [],

81 sponsees: [],

82 }, data.slice(1)];

83 if (data[0] !== '[') throw new Error('Invalid children in data: ' + data.slice(0, 20));

85 let endFound = false;

86 let counter = 0;

87 data = data.slice(1);

88 const children = [];

89 const sponsees = [];

90 while (!endFound && data.length && counter < 20000) {

91 if (data[0] === ']') {

92 endFound = true;

93 data = data.slice(1);

94 } else {

95 let sub;

96 [sub, data] = this.extractChartPoint(data);

97 if (!sub.parent || sub.parent === sup)

98 children.push(sub);

99 if (sub.sponsor === undefined || sub.sponsor === sup)

100 sponsees.push(sub);

101 }

102 counter++;

103 }

104 return [{ children, sponsees }, data];

105 }

106

107 extractChartPoint(data: string): [ChartPoint, string] {

108 let point, subs;

109 [point, data] = this.extractMeta(data);

110 [subs, data] = this.extractChildren(data, point.patp);

111 point = {

112 ...point,

113 ...subs,

114 };

115 return [point, data];

116 }

117

118 linkChartData(points: ChartPoint[], store: any): ChartPoint[] {

119 if (!points) return points;

120 return points.map(point => {

121 if (!store[point.patp]) return point;

122 if (!point.children?.length) {

123 point.children = this.linkChartData(store[point.patp].children, store);

124 let picked = point.children.filter(child => child.picked || child.pickedChildren);

125 point.pickedChildren = picked.length > 0;

126 }

127 if (!point.sponsees?.length) {

128 point.sponsees = this.linkChartData(store[point.patp].sponsees, store);

129 let picked = point.sponsees.filter(child => child.picked || child.pickedSponsees);

130 point.pickedSponsees = picked.length > 0;

131 }

132 return point;

133 });

134 }

135

136 parse(str: string): ChartSubs {

137 if (!str) return { children: [], sponsees: [] };

138 let [{ children: baseChildren }, _] = this.extractChildren(str, undefined);

139 let store = {};

140 baseChildren.forEach(child => {

141 store[child.patp] = {

142 children: child.children,

143 sponsees: child.sponsees,

144 };

145 });

146 let base: ChartPoint = {

147 patp: '~base',

148 dominion: 'l1',

149 picked: true,

150 }

151

152 let points = this.linkChartData([base], store);

153 return {

154 children: points[0].children || [],

155 sponsees: points[0].sponsees || [],

156 }

157 }

158}

159

160export function parseChartData(data: string, filter: Set<string>): ChartSubs {

161 let start = Date.now();

162 let parser = new ChartDataParser(filter);

163 let parsed = parser.parse(data);

164 // console.log(`finished parsing chart data to js object in ${Date.now() - start} ms`);

165 return parsed;

166}

167

168const circle = 2 * Math.PI;

169function chordLength(radius, radians) {

170 return 2 * radius * Math.sin(radians / 2);

171}

172function distancePolar(r1, th1, r2, th2) {

173 return Math.sqrt((r1 * r1) + (r2 * r2) - (2 * r1 * r2 * Math.cos(th2 - th1)));

174}

175export function arrangePointsInSpirals(

176 numPoints,

177 {

178 maxDistance, minDistance,

179 startX = 0, startY = 0,

180 maxArms = 6, maxPerArm = 45,

181 makeSingleArmCircle = false,

182 }): { coords: any[], numArms: number, minDistanceBetween: number } {

183 const numSmallEnoughArms = Math.ceil(numPoints / maxPerArm);

184 let eRootNumArms = Math.max(1, Math.floor(Math.pow(numPoints, 1 / Math.E)));

185 const numArms = Math.max(numSmallEnoughArms, eRootNumArms);

186 const singleArmCircle = makeSingleArmCircle && numArms === 1;

187 const numPerArm = numPoints / numArms;

188 let armThetaRange = numPerArm * Math.min(Math.PI / 12, 0.25 * circle / numArms);

189 if (singleArmCircle) {

190 minDistance = maxDistance;

191 armThetaRange = circle;

192 }

193 const distanceRange = maxDistance - minDistance;

194 const pointWeight = 1 / numPerArm;

195 let minDistanceBetween = distancePolar(minDistance, 0,

196 minDistance + distanceRange * pointWeight, armThetaRange * pointWeight);

197 if (numPoints <= 3) minDistanceBetween = maxDistance * 0.75;

198 const coords = [];

199 let lastArm = null;

200 let indexInArm = null;

201 for (let i = 0; i < numPoints; i++) {

202 const overallProgress = i / numPoints;

203 const arm = Math.floor(numArms * overallProgress);

204 if (lastArm === arm) {

205 indexInArm++;

206 } else {

207 indexInArm = 0;

208 }

209 const interArmProgress = arm / numArms;

210 const beginningOfNextArm = Math.floor(numPerArm * (arm + 1));

211 const numInThisArm = beginningOfNextArm - (i - indexInArm);

212 const intraArmProgress = indexInArm / numInThisArm;

213 const theta = circle * interArmProgress + armThetaRange * intraArmProgress;

214 let line = (minDistance + distanceRange * intraArmProgress);

215 let x = 0 + startX + line * Math.cos(theta);

216 let y = 0 + startY + line * Math.sin(theta);

217 coords.push({

218 coords: [x, y],

219 arm: singleArmCircle ? i : arm,

220 });

221 lastArm = arm;

222 };

223 return {

224 coords,

225 numArms,

226 minDistanceBetween,

227 };

228}

229type childKey = ('sponsees' | 'children');

230export function populateGraph(g: Graph, chartSubs: ChartSubs, subsKey: childKey, callback?): Graph {

231 let pickedSubsKey = subsKey == 'children' ? 'pickedChildren' : 'pickedSponsees';

232 function pickedColor(point: ChartPoint, normal: string) {

233 return point.picked ? normal : (point[pickedSubsKey] ? colors.SUB_PICKED : colors.NOT_PICKED);

234 }

235 function pickedArmColor(point: ChartPoint, normal: string) {

236 return point[pickedSubsKey] ? normal : colors.NOT_PICKED;

237 }

238 let points = chartSubs[subsKey];

239 if (!(points instanceof Array)) return;

240 if (!g) {

241 g = new Graph();

242 } else {

243 g.clear();

244 }

245

246 let sponsorEdges = [];

247

248 let offsetX = 0;

249 let offsetY = 0;

250

251 let a = 120000000;

252 let b = 9000000;

253 let theta = 0;

254

255 points.forEach((galaxy, gi) => {

256 offsetX = 0 + (a + b * theta) * Math.cos(theta);

257 offsetY = 0 + (a + b * theta) * Math.sin(theta);

258

259 theta = 0.15 * (gi+1) * (1 - .15 * (gi / 256));

260 const gPatp = galaxy.patp;

261 const itsYou = gPatp === '~' + window.ship;

262 g.addNode(gPatp, {

263 label: gPatp,

264 size: 3,

265 color: itsYou ? colors.YOU : pickedColor(galaxy, colors.WHITE),

266 x: offsetX,

267 y: offsetY,

268 zIndex: 10,

269 });

270

271 const stars = galaxy[subsKey] || [];

272 const numStars = stars.length;

273 const maxStarDistance = 60000 * 128;

274 const minStarDistance = maxStarDistance / 4;

275 const starSize = 1.2 / Math.pow(numStars, 1 / 7);

276 const {

277 coords: starCoords,

278 numArms: numStarArms,

279 minDistanceBetween: minDistanceBetweenStars,

280 } = arrangePointsInSpirals(numStars,

281 {

282 maxDistance: maxStarDistance,

283 minDistance: minStarDistance,

284 startX: offsetX,

285 startY: offsetY,

286 makeSingleArmCircle: true,

287 });

288 let lastStarArm = null;

289 let lastStarPatp = null;

290 let GSarmColor = pickedArmColor(galaxy, colors.LGREY)

291 stars.forEach((star, si) => {

292 const sPatp = star.patp;

293

294 const [starX, starY] = starCoords[si].coords;

295 const arm = starCoords[si].arm;

296

297 const itsYou = sPatp === '~' + window.ship;

298 if (itsYou) {

299 g.setNodeAttribute(gPatp, 'color', colors.YOUR_GAL);

300 }

301 try {

302 g.addNode(sPatp, {

303 label: sPatp,

304 size: starSize,

305 color: itsYou ? colors.YOU : pickedColor(star, colors.GOLDT2),

306 x: starX,

307 y: starY,

308 zIndex: 8,

309 });

310 if (lastStarArm == arm) {

311 g.addEdge(sPatp, lastStarPatp, {

312 color: GSarmColor,

313 size: 0.1,

314 zIndex: 7,

315 });

316 } else {

317 g.addEdge(sPatp, gPatp, {

318 color: GSarmColor,

319 size: 0.2,

320 zIndex: 9,

321 });

322 }

323 lastStarArm = arm;

324 lastStarPatp = sPatp;

325 if (star.sponsor) {

326 sponsorEdges.push([sPatp, star.sponsor, {

327 color: colors.GREEN,

328 size: 0.2,

329 zIndex: 11,

330 }]);

331 }

332

333 const planets = star[subsKey] || [];

334 const numPlanets = planets.length;

335 // const maxPlanetDistance = starSize * 1.6 * 4000 * 64;

336 const maxPlanetDistance = minDistanceBetweenStars * 0.45;

337 const minPlanetDistance = maxPlanetDistance / 4;

338 const {

339 coords: planetCoords,

340 numArms: numPlanetArms,

341 minDistanceBetween: minDistanceBetweenPlanets,

342 } = arrangePointsInSpirals(numPlanets,

343 {

344 maxDistance: maxPlanetDistance,

345 minDistance: minPlanetDistance,

346 startX: starX,

347 startY: starY,

348 maxArms: 30,

349 makeSingleArmCircle: true,

350 });

351 let lastPlanetArm = null;

352 let lastPlanetPatp = null;

353 let SParmColor = pickedArmColor(star, colors.DGREY)

354 planets.forEach((planet, pi) => {

355 const pPatp = planet.patp;

356 const [planetX, planetY] = planetCoords[pi].coords;

357 const arm = planetCoords[pi].arm;

358 const planetSize = Math.sqrt(Math.min(minPlanetDistance, minDistanceBetweenPlanets)) / 1300;

359 const planetEdgeSize = planetSize / 3;

360 const itsYou = pPatp === '~' + window.ship;

361 if (itsYou) {

362 g.setNodeAttribute(sPatp, 'color', colors.YOUR_STAR);

363 g.setNodeAttribute(gPatp, 'color', colors.YOUR_GAL);

364 }

365 try {

366 g.addNode(pPatp, {

367 label: pPatp,

368 size: planetSize,

369 color: itsYou ? colors.YOU : pickedColor(planet, planet.dominion == 'l2' ? colors.GREEN : colors.BLUE),

370 x: planetX,

371 y: planetY,

372 zIndex: 6,

373 });

374 if (lastPlanetArm == arm) {

375 g.addEdge(pPatp, lastPlanetPatp, {

376 color: SParmColor,

377 size: planetEdgeSize,

378 zIndex: 5,

379 });

380 } else {

381 if (numPlanetArms == 1) {

382 g.addEdge(pPatp, sPatp, {

383 color: SParmColor,

384 size: planetEdgeSize,

385 zIndex: 5,

386 });

387 }

388 }

389 if (planet.sponsor) {

390 sponsorEdges.push([pPatp, planet.sponsor, {

391 color: colors.GREEN,

392 size: planetEdgeSize,

393 zIndex: 11,

394 }]);

395 }

396 lastPlanetArm = arm;

397 lastPlanetPatp = pPatp;

398 } catch (e) {

399 let msg = `Couldn't add ${pPatp} to the graph`;

400 console.error(msg, e);

401 alertMe(msg + '\n' + e.message);

402 }

403 });

404 } catch (e) {

405 let msg = `Couldn't add ${sPatp} to the graph`;

406 console.error(msg, e);

407 alertMe(msg + '\n' + e.message);

408 }

409 });

410 });

411 sponsorEdges.forEach(([point, sponsor, attrs]) => {

412 // g.addEdge(point, sponsor, attrs);

413 });

414 if (callback) {

415 setTimeout(callback, 0);

416 }

417 return g;

418}

419

420function alertMe(msg: string) {

421 alert('Encountered an error, please tell ~midlev-mindyr: ' + msg);

422}