Sachverhalt:
A.
A._ ist Eigentümer der Parzelle Nr. 570 in Walzenhausen. B._ ist Eigentümer der benachbarten Parzelle Nr. 1698, auf der er ein Einfamilienhaus errichtet hat. Dabei hat er nach Ansicht von A._ zahlreiche Bauvorschriften verletzt. Den kommunalen Behörden wirft A._ Untätigkeit vor, weshalb er am 13. März 2020 eine Strafanzeige gegen B._ bzw. gegen unbekannte Behördenmitglieder der Baukommission Walzenhausen oder der Gemeinde Walzenhausen wegen mehrfacher Widerhandlung gegen das Baugesetz bzw. wegen Verletzung der Amtspflicht und Begünstigung bei der Staatsanwaltschaft Appenzell Ausserrhoden eingereicht hat. A._ führte aus, er konstituiere sich in diesem Verfahren als Geschädigter und mache gegenüber der Täterschaft eine Zivilforderung geltend, deren Höhe noch bekannt gegeben werde. Mit Verfügung vom 17. November 2020 sistierte die Staatsanwaltschaft das Verfahren gegen B._ betreffend mehrfacher Widerhandlung gegen das Baugesetz gestützt auf <ref-law> in Verbindung mit <ref-law>.
B.
Am 30. November 2020 erhob A._ Beschwerde gegen diese Sistierungsverfügung beim Obergericht des Kantons Appenzell Ausserrhoden. Mit Verfügung vom 22. Februar 2021 trat dieses nicht darauf ein.
C.
Dagegen erhebt A._ am 19. April 2021 Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, die angefochtene Verfügung des Obergerichts vom 22. Februar 2021 aufzuheben und die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. Allenfalls sei die Sache zur Fortführung der Strafuntersuchung ohne unbegründete Verzögerungen an die Staatsanwaltschaft und an das Obergericht zur Neuverlegung der Kosten- und Entschädigungsfolgen im vorinstanzlichen Beschwerdeverfahren zurückzuweisen.
Die Staatsanwaltschaft Appenzell Ausserrhoden wie auch B._ beantragen, die Beschwerde abzuweisen, soweit darauf einzutreten ist. B._ beantragt weiter, die Angelegenheit allenfalls zur Neubeurteilung an das Obergericht zurückzuweisen. Das Obergericht verzichtet auf Vernehmlassung.

Erwägungen:
1.
Das Bundesgericht prüft seine Zuständigkeit und die Zulässigkeit der Beschwerde von Amtes wegen und mit freier Kognition (<ref-law>; <ref-ruling> E. 2; <ref-ruling> E. 1; je mit Hinweisen). Immerhin sind die sachverhaltlichen Grundlagen, auf welche sich die Zulässigkeit einer Beschwerde stützt, vom Beschwerdeführer darzulegen, soweit sie nicht auf der Hand liegen, namentlich auch in Bezug auf die Legitimation (<ref-ruling> E. 1).
1.1. Die Beschwerde richtet sich gegen einen Nichteintretensentscheid einer letzten kantonalen Instanz (<ref-law>), der im Rahmen eines Strafverfahrens ergangen ist. Dagegen kann grundsätzlich Beschwerde in Strafsachen (<ref-law>) erhoben werden.
1.2. Unabhängig davon, ob es sich beim angefochtenen erstinstanzlichen Entscheid um einen Zwischen- oder einen Endentscheid handelt, ist der Beschwerdeführer, auf dessen Beschwerde die letzte kantonale Instanz nicht eingetreten ist, im Sinne von <ref-law> vor Bundesgericht beschwerdeberechtigt. Soweit sich die Beschwerde auf die Frage der Zulässigkeit einer kantonalen Beschwerde bezieht, tritt das Bundesgericht nämlich unabhängig vom Erfordernis eines nicht wieder gutzumachenden Nachteils im Sinne von <ref-law> darauf ein (<ref-ruling> E. 1.2; <ref-ruling> E. 1.1; Urteil des Bundesgerichts 1B_362/2021 vom 6. September 2021 E. 1.2; je mit Hinweisen).
1.3. Der Streitgegenstand vor Bundesgericht ist auf die Eintretensfrage beschränkt. Die Behandlung der Eintretensfrage ist im Ergebnis aufgrund der nachfolgenden Erwägungen nicht zu beanstanden, weshalb auf die darüber hinaus gehenden Rügen des Beschwerdeführers gegen die vorinstanzliche Eventualbegründung nicht einzutreten ist.
2.
Streitig ist, ob die Vorinstanz zu Recht auf die Beschwerde nicht eingetreten ist.
2.1. Der Beschwerdeführer macht geltend, die Vorinstanz habe mit ihrem Nichteintretensentscheid in mehrfacher Hinsicht das Willkürverbot (<ref-law>) und seinen Anspruch auf rechtliches Gehör (<ref-law>) verletzt sowie eine formelle Rechtsverweigerung (<ref-law>, Art. 6 Ziff. 1 EMRK) begangen.
2.2. Jede Partei, die ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung eines Entscheids hat, kann ein Rechtsmittel ergreifen (<ref-law>). Partei ist namentlich die Privatklägerschaft (<ref-law>). Als solche gilt die geschädigte Person, die im Sinne von <ref-law> erklärt, sich am Strafverfahren als Straf- oder Zivilklägerin zu beteiligen, wobei der Strafantrag dieser Erklärung gleichgestellt ist. Als "geschädigt" gilt die Person, die durch die Straftat in ihren Rechten unmittelbar verletzt worden ist (<ref-law>). Unmittelbar verletzt und damit in eigenen Rechten betroffen ist, wer Träger des durch die verletzte Strafnorm geschützten oder zumindest mitgeschützten Rechtsguts ist (<ref-ruling> E. 2.3 mit Hinweis). Zivilforderungen sind keine notwendige Voraussetzung für die Rechtsmittellegitimation im kantonalen Verfahren bzw. für die Bejahung der strafrechtlichen Geschädigtenstellung nach <ref-law> und die Beteiligung am Strafverfahren als Strafkläger (<ref-ruling> E. 2.2.2; <ref-ruling> E. 2.3.1; <ref-ruling> E. 3.3.3; je mit Hinweisen).
Im Zusammenhang mit Strafnormen, die nicht primär Individualrechtsgüter schützen, gelten praxisgemäss nur diejenigen Personen als Geschädigte, die durch die darin umschriebenen Tatbestände in ihren Rechten beeinträchtigt werden, sofern diese Beeinträchtigung unmittelbare Folge der tatbestandsmässigen Handlung ist. Bei Straftaten gegen kollektive Interessen reicht es für die Annahme der Geschädigtenstellung im Allgemeinen aus, dass das von der geschädigten Person angerufene Individualrechtsgut durch den Straftatbestand auch nur nachrangig oder als Nebenzweck geschützt wird. Werden durch Delikte, die (nur) öffentliche Interessen verletzen, private Interessen auch, aber bloss mittelbar beeinträchtigt, so ist die betroffene Person nicht Geschädigte im Sinne von <ref-law> (<ref-ruling> E. 2.3.1 mit Hinweis).
2.3. Die Vorinstanz prüfte daher die Rechtsnatur des Tatbestandes der Widerhandlung gegen das Gesetz des Kantons Appenzell Ausserrhoden über die Raumplanung und das Baurecht vom 12. Mai 2003 (BauG/AR; bGS 721.1). Sie führte aus, dass gemäss Art. 122 Abs. 1 BauG/AR vorsätzliche und fahrlässige Widerhandlungen gegen die Vorschriften dieses Gesetzes, die Baureglemente der Gemeinden sowie deren Ausführungserlasse mit Busse von Fr. 500.-- bis zu Fr. 50'000.-- geahndet würden. Strafbar seien insbesondere auch die Ausführungen von Bauten ohne Bewilligung, die Abweichung von bewilligten Plänen sowie die Missachtung von Bedingungen und Auflagen. Die Vorinstanz erwog, dass Bauvorschriften nicht immer nur öffentliche Interessen schützen würden, sie könnten ausser den Interessen der Allgemeinheit auch oder in erster Linie dem Schutz der Nachbarn dienen. Nach der Rechtsprechung komme den Bestimmungen über die äusseren Abmessungen der Gebäude und die Ausnützung des Bodens auch eine nachbarschützende Funktion zu. Voraussetzung sei allerdings, dass der Nachbar durch die behauptete widerrechtliche Auswirkung der Baute unmittelbar betroffen werde und dies durch den Beschwerdeführer auch dargetan werde. Es obliege dem Rechtsmittelkläger, seine Parteistellung und die damit verbundene Legitimation darzulegen bzw. rechtsgenügend zu begründen, was vorliegend nicht der Fall sei.
2.4. Diese vorinstanzlichen Erwägungen sind im Ergebnis nicht zu beanstanden. Vorliegend fraglich war, ob die geltend gemachten Delikte den Beschwerdeführer unmittelbar beeinträchtigen bzw. beeinträchtigt haben. Nach <ref-law> muss der Beschwerdeführer die Tatsachen darlegen, aus denen sich seine Beschwerdeberechtigung ergeben soll, sofern sie nicht offensichtlich sind (<ref-ruling> E. 1.3 mit Hinweisen). Es obliegt damit dem Beschwerdeführer darzulegen und zu begründen, dass diese Voraussetzung seiner Beschwerdelegitimation vorliegt (vgl. VIKTOR LIEBER, in: Donatsch/Lieber/Summers/Wohlers, Kommentar zur Schweizerischen Strafprozessordnung, 3. Aufl. 2020, N. 1a zu <ref-law>).
Die Vorinstanz argumentiert, der Beschwerdeführer mache im Wesentlichen geltend, der Beschwerdegegner habe sein Einfamilienhaus nicht nach den genehmigten Plänen errichtet und er habe eine Frischwasserleitung zu seinem Haus an einem nicht genehmigten Ort verlegt. Die beanstandeten Abweichungen vom Baugesuch habe der Beschwerdeführer in einer Tabelle zusammengefasst. Inwiefern der Beschwerdeführer in seinen Rechten beeinträchtigt sein soll, erschliesse sich daraus jedoch nicht. Einzelne, vom Beschwerdeführer geltend gemachte Abweichungen seien zudem so geringfügig, dass die Geschädigtenstellung des Beschwerdeführers dadurch nicht bejaht werden könne. Auf einem Foto habe er, so die Vorinstanz, die angeblich offenkundigen Abweichungen gegenüber dem bewilligten Baugesuch mit roter Farbe markiert. Es sei jedoch nicht einsehbar, inwiefern hier die nach bundesgerichtlicher Rechtsprechung massgeblichen äusseren Abmessungen des Gebäudes oder die Ausnützung des Bodens in einem rechtlich relevanten Ausmass verletzt sein sollen. Inwiefern der Beschwerdeführer überdies durch die angeblich unrechtmässig erstellte Wasserleitung, die nicht durch seine Liegenschaft führt, geschädigt sein soll, erschliesse sich nicht. Der Beschwerdeführer lege in der Beschwerde nicht rechtsgenüglich dar, warum er durch die angebliche Nichteinhaltung der Bauvorschriften durch den Beschwerdegegner geschädigt oder zumindest in seinen Rechten beeinträchtigt sein soll.
Der Beschwerdeführer dringt mit seinen Vorbringen gegen diese Ausführungen nicht durch. Die von ihm betonte Eigenschaft als Nachbar und seine darauf gestützte Beschwerdelegitimation im verwaltungsrechtlichen Verfahren führen nicht dazu, dass er auch im Strafverfahren beschwerdelegitimiert ist. Entgegen seiner Ansicht begründet die Vorinstanz ihr Nichteintreten zudem nachvollziehbar; dass sie dabei willkürlich gehandelt haben könnte, ist nicht ersichtlich. Um die Unmittelbarkeit der Beeinträchtigung durch die geltend gemachten Delikte zu prüfen, stützte sie sich nicht bloss auf die diesbezüglich ungenügenden Ausführungen in der Beschwerdeschrift ab. Vielmehr untersuchte sie die Akten im Hinblick auf die Unmittelbarkeit der Beeinträchtigung des Beschwerdeführers durch die geltend gemachten Delikte und seine allfällig begründbare Beschwerdelegitimation, was eigentlich er hätte darlegen müssen (vorne E. 2.4 a.A.). Damit ist auch nicht ersichtlich, dass der Anspruch des Beschwerdeführers auf rechtliches Gehör verletzt sein oder die Vorinstanz eine formelle Rechtsverweigerung begangen haben könnte. Es ist dem Beschwerdeführer immerhin beizupflichten, dass die Bemerkung der Vorinstanz, der Beschwerdeführer habe "bezeichnenderweise" bisher auch keine Zivilforderung beziffert oder auch nur begründet, problematisch ist, da Zivilforderungen wie erwähnt (vorne E. 2.2) keine notwendige Voraussetzung für die Rechtsmittellegitimation im kantonalen Verfahren bzw. für die Bejahung der strafrechtlichen Geschädigtenstellung nach <ref-law> und die Beteiligung am Strafverfahren als Strafkläger bilden. Da diese Bemerkung für die Begründung des vorinstanzlichen Nichteintretensentscheids entbehrlich ist, vermag sie nichts an der Beurteilung der Rechtmässigkeit des angefochtenen Entscheids zu ändern.
2.5. Die Vorinstanz hat durch ihren Nichteintretensentscheid die geltend gemachten Garantien nicht verletzt.
3.
Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem unterliegenden Beschwerdeführer aufzuerlegen (<ref-law>). Überdies hat er den obsiegenden, anwaltlich vertretenen Beschwerdegegner für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Staatsanwaltschaft des Kantons Appenzell A.Rh. und dem Obergericht Appenzell Ausserrhoden, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 12. Januar 2022
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Jametti
Der Gerichtsschreiber: Bisaz