Erwägungen:
1.
Die Y1._ reichte dem Tiefbauamt des Kantons Basel-Stadt am 26. April 2018 ein generelles Baubegehren für ein Quartierparking auf der Parzelle 0825/0799 (Quartierparking Landhof) ein. Dagegen wurden zahlreiche Einsprachen erhoben. Mit Entscheid vom 12. September 2018 wies das Tiefbauamt die Einsprachen ab. Einen dagegen gerichteten Rekurs wies die Baurekurskommission des Kantons Basel-Stadt am 27. März 2019 ab.
Gegen den Entscheid der Baurekurskommission erhoben 93 Personen Rekurs ans Appellationsgericht des Kantons-Basel Stadt. Mit Urteil vom 3. Dezember 2020 wies dieses ihr Rechtsmittel ebenfalls ab. In Bezug auf fünf Personen, die den Rekurs zurückgezogen hatten, schrieb es das Verfahren dagegen ab.
2.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht vom 1. Februar 2021 beantragen die im Rubrum genannten Personen im Wesentlichen, das Urteil des Appellationsgerichts sei aufzuheben.
3.
Im Rahmen des Schriftenwechsels erwähnten die Beschwerdeführer, sie hätten der Presse entnommen, dass die Bauherrschaft das Projekt nicht mehr umsetzen wolle. Die Beschwerdegegnerin bestätigte dies mit Eingabe vom 3. Juni 2021. Die Beschwerdeführer hätten die Behörden jedoch derart mit Vorwürfen eingedeckt, dass trotzdem ein Interesse an einer höchstrichterlichen Beurteilung weiterbestehe. Zudem stelle sich noch an anderen Orten in Basel die gleiche Frage.
4.
In der Folge teilte das Bundesgericht den Verfahrensbeteiligten mit, das Verfahren scheine gegenstandslos geworden zu sein, und räumte ihnen Gelegenheit zur Stellungnahme ein. Die Baurekurskommission hat auf eine Vernehmlassung zur Frage der Gegenstandslosigkeit verzichtet und die Beschwerdegegnerin hat sich nicht vernehmen lassen. Die Beschwerdeführer begrüssen eine Abschreibung des Verfahrens und beantragen, die Kosten des bundesgerichtlichen und der vorinstanzlichen Verfahren der Beschwerdegegnerin aufzuerlegen und diese zu verpflichten, ihnen eine angemessene Parteientschädigung auszurichten. Das Appellationsgericht weist darauf hin, dass bei einer Abschreibung des Verfahrens das Urteil vom 3. Dezember 2020 unbesehen der Desinteresseerklärung der Bauherrschaft in Rechtskraft erwachsen würde. Sollte das Bundesgericht dieses Urteil aufheben, werde beantragt, den Kostenpunkt davon auszunehmen. Das Tiefbauamt ist der Auffassung, das Verfahren könne nur dann als gegenstandslos abgeschrieben werden, wenn im Schreiben der Beschwerdegegnerin vom 3. Juni 2021 eine unmissverständliche Prozesserklärung zu sehen sei, wonach sie ihr Baugesuch unwiderruflich zurückziehe. Andernfalls würde der angefochtene generelle Bauentscheid in Rechtskraft erwachsen. Die Beschwerdeführer haben eine weitere Stellungnahme eingereicht.
5.
Mit ihrem Schreiben vom 3. Juni 2021 hat die Beschwerdegegnerin erklärt, das Projekt, das Gegenstand des generellen Baugesuchs bildet, nicht umsetzen zu wollen. Damit ist das bundesgerichtliche Verfahren gegenstandslos geworden und als erledigt abzuschreiben (<ref-law>). Ebenso sind die vorangehenden kantonalen Verfahren gegenstandslos geworden, was im Dispositiv festzuhalten ist (vgl. Urteile 1C_69/2016 vom 13. Oktober 2016; 1C_301/2013 vom 19. November 2013). Ob sich an anderen Orten in Basel gleiche Fragen stellen, ist insofern ebenso belanglos wie der von der Beschwerdegegnerin erhobene Vorwurf, die Beschwerdeführer hätten die Behörden mit Vorwürfen eingedeckt. Ein fortbestehendes Rechtsschutzinteresse lässt sich damit nicht begründen.
6.
Erklärt das Bundesgericht einen Rechtsstreit als gegenstandslos, entscheidet es mit summarischer Begründung über die Prozesskosten aufgrund der Sachlage vor Eintritt des Erledigungsgrundes (<ref-law> in Verbindung mit <ref-law> [SR 273]). Bei der Beurteilung der Kosten- und Entschädigungsfolgen ist somit in erster Linie auf den mutmasslichen Ausgang des Prozesses abzustellen (<ref-ruling> E. 8.2; <ref-ruling> E. 2a; je mit Hinweisen). Allerdings ist es beim Rückzug eines Baugesuchs in der Regel gerechtfertigt, den Baugesuchsteller die Kosten- und Entschädigungsfolgen (sowohl des bundesgerichtlichen als auch der vorinstanzlichen Verfahren) gestützt auf das Verursacherprinzip tragen zu lassen (Art. 66 Abs. 3 und Art. 68 Abs. 4 BGG; Urteile 1C_69/2016 vom 13. Oktober 2016 E. 2; 1C_301/ 2013 vom 19. November 2013 E. 2 f.; je mit Hinweisen).
7.
Die Kosten des bundesgerichtlichen Verfahrens sind somit der Beschwerdegegnerin aufzuerlegen. Dasselbe gilt für die Kosten des Verfahrens vor der Baurekurskommission und dem Appellationsgericht. Die Beschwerdegegnerin hat zudem den Beschwerdeführern für das bundesgerichtliche und das kantonale Verfahren eine angemessene Parteientschädigung zu bezahlen.

Demnach erkennt der Einzelrichter:
1.
Das Verfahren 1C_69/2021 wird als gegenstandslos geworden vom Geschäftsverzeichnis abgeschrieben.
2.
Es wird festgestellt, dass die vorangehenden Verfahren vor dem Tiefbauamt, der Baurekurskommission und dem Appellationsgericht ebenfalls gegenstandslos geworden sind.
3.
Die Kosten des Verfahrens vor Bundesgericht von Fr. 1'000.--, des Verfahrens vor dem Appellationsgericht von Fr. 3'000.-- und des Verfahrens vor der Baurekurskommission von Fr. 2'500.-- werden der Beschwerdegegnerin auferlegt.
4.
Die Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 4'000.-- und für das kantonale Verfahren mit insgesamt Fr. 6'000.-- zu entschädigen.
5.
Diese Verfügung wird den Parteien, dem Tiefbauamt Basel-Stadt, Allmendverwaltung, der Baurekurskommission des Kantons Basel-Stadt und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 19. Oktober 2021
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Einzelrichter: Haag
Der Gerichtsschreiber: Dold