Pathfinding Research

My understanding of the pathfinding data block so far. This is being written as a reminder and as a guideline for anyone else interested in the subject. Hopefully I can expand this list in the future with more details to fully
uncover how this system works. Follow the images to use as reference for the list.

Pathfinding seems to be setup in a very particular way. While you can reuse some of the collision data for pathfinding the pathfinding mesh and the collision mesh are not 1:1. The pathfinding mesh for the main BSP is mostly only
floor with cut outs for instance geometry. Instance geo, scenery, and device machines are given full 3D meshes in the pathfinding mesh

Example image of a sector from 01bsp_outro in 01b_spacestation: https://i.imgur.com/x5lMcbo.png
Image 1: https://i.imgur.com/2C43nd8.png
1. The begining of everything. This obviously needs to exist in order to write our other data. Only one should ever exist.

2. Sectors. These are shapes in the pathfinding mesh. The pathfinding mesh for the main BSP appears to only ever cover the floor as seen in the reference images in aiide05.ppt and extracted pathfinding meshes from the campaign. There
is a certain angle where parts of the mesh are just culled. Possibly around 60-90 degrees. Originally has some method to detect instance geometry cutting through the main mesh and build a sort of bounding area around it. Likely to
make the links around the instance geo have certain properties so that the AI was aware. This is talked about briefly in slide 9. Sectors seem to be ngons and can take as many vertices as needed to make the specific shape needed.

Example image of sectors from aiide05.ppt: https://i.imgur.com/sxTdM8k.png

3. This is a flag for defining the sector. Appears to allow the AI to walk inside that sector.

4. This is a flag for defining the sector. This might be decided if the attached surface has the "breakable surface" flag checked.

5. This is a flag for defining the sector. This might be for device machines with attached pathfinding meshes that are allowed to move such as the gondola from 05a_deltaapproach or the Scarab from 03b_newmombasa.

Example image of pathfinding mesh on Scarab: https://i.imgur.com/ufTxYaW.png

6. This is a flag for defining the sector. The purpose that this serves is unknown. Speculation at the moment from me is that this flag might be used if the mesh in question is part of the main BSP and not say scenery or instance geo.

7. This is a flag for defining the sector. Used mostly on flat geometry but what that entails in unknown.

8. This is a flag for defining the sector. The purpose that this serves is unknown.

9. This is a flag for defining the sector. The purpose that this serves is unknown.

10. This is a flag for defining the sector. The purpose that this serves is unknown.

11. This is a flag for defining the sector. The purpose that this serves is unknown.

12. This is a flag for defining the sector. The purpose that this serves is unknown.

13. This is a flag for defining the sector. The purpose that this serves is unknown. Haven't seen it used.

14. This is a flag for defining the sector. The purpose that this serves is unknown.

15. This is a flag for defining the sector. The purpose that this serves is unknown.

16. This is a flag for defining the sector. The purpose that this serves is unknown.

17. This is an index referencing an unknown tag block at the moment. If an index isn't being referenced then it should always be -1.

18. The first link that begins forming the shape of the sector. The link will reference all the relevant links to give shape to the sector and the next sector will reference the next link after the last link. So for example having
two square shaped sectors will give you 8 total links. The first sector will start at 0 and the second sector will start at 4.

19 Links are what connect two points to give shape to to that sector. It has several options that mirror sectors in some aspects. There can be thousands of these.

20. This is the first point in the link. The number is the index of the vertice tag block.

21. This is the second point in the link. The number is the index of the vertice tag block.

22. This is a flag for defining the link. The purpose that this serves is unknown.

23. This is a flag for defining the link. The purpose that this serves is unknown.

24. This is a flag for defining the link. The purpose that this serves is unknown.

25. This is a flag for defining the link. The purpose that this serves is unknown.

26. This is a flag for defining the link. The purpose that this serves is unknown.

27. This is a flag for defining the link. The purpose that this serves is unknown.

28. This is a flag for defining the link. The purpose that this serves is unknown. Speculation at the moment from me but this might be related to things not attached to the main BSP mesh

29. This is a flag for defining the link. The purpose that this serves is unknown.

30. This is a flag for defining the link. The purpose that this serves is unknown.

31. This is a flag for defining the link. This would probably check the angle of the surface by checking the link that meets of the sector that meets the current link we want to set the flag on. If it's around 90 then it's a wall.

Example image to be more clear: https://i.imgur.com/QEZG2tT.png

32. This is a flag for defining the link. Same as the previous example though we would check if the angle is -90

33. This is a flag for defining the link. If it's a wall then it likely has this checked. Would maybe also use planes to see how far it goes and check if it has enough space to be leanable?

34. This is a flag for defining the link. The purpose that this serves is unknown.

35. This is a flag for defining the link. The purpose that this serves is unknown.

36. This is an index referencing an unknown tag block at the moment. If an index isn't being referenced then it should always be -1.

37. The next link that makes up shape of the sector. Get this by finding out how many links makes up the sector by comparing the first link of your current sector to the next sectors's first link to build a range. If the next sector is 4 then the range is 0-3 and the forward link is 1. To be exact the forward link is the current index +1

38. The last link that makes up the sector. Get this by finding out how many links makes up the sector by comparing the first link of your current sector to the next sectors's first link to build a range. If the next sector is 4 then the range is 0-3 and the reverse link is 3. To be exact the reverse link is the current index -1

39. The sector the links are giving shape to. Find this by finding out what sector the current link belongs to. This sector will be your left sector.

40. The sector that link is meeting. Find this by finding a link with matching vertex indexes. After finding this matching link then find what sector it belongs to. The sector it belongs to will be the right sector. The indexes could be the same or inverse

Image 2: https://i.imgur.com/vongKZX.png

41. The index of the ref block. The purpose of this block is to attach a sector to a pathfinding mesh by matching the index of the ref to the surface index in collision.

42. An integer that references a sector by its index. It seems to have two different ways of doing this. Either a whole positive value for a single sector or a negative and extremely high number like -24123156423 when it seems to be referencing a BSP node.

43. The index of the BSP nodes. Unsure what these two or how they work. A way to simplify complicated geometry in some way?

44. Unsure what this is. Some type of rotation?

45. The purpose that this serves is unknown.

46. The purpose that this serves is unknown.

47. The purpose that this serves is unknown. This tag block is not filled in any map that has pathfinding data. Might do nothing and just be unused?

48. What 47 said

49. The index of a vertice. A single block in this area is a single vertice in the pathfinding mesh.

50. The XYZ coordinates of the vertice in the mesh. Follows the same rule as any other mesh in Halo 2 where the vertice translation is divided by 100. So 100 Blender units is 1 world unit.

51. An index in this tag block. Appears to be related to scenery and device machine meshes.

52. A flag stating if it is mobile or not. Perhaps it would have checked if the object had an animation?

53. The purpose that this serves is unknown.

54. The purpose that this serves is unknown.

55. An index in this tag block. Appears to be what works the pathfinding meshes of the object in question to their location?

56. Not sure what this is exactly. Does not appear to be just a BSP index. Some values go as high as 33554436. Unsure as to what this could be referencing. I've considered that it could be the unique ID the scenery and device machines have but I am not sure.

57. The purpose that this serves is unknown.

58. The purpose that this serves is unknown.

59. The purpose that this serves is unknown.